computing the largest empty convex subset of a set of points
A largest empty convex subset of a finite set of points, S, is a maximum cardinality subset of S, that (1) are the vertices of a convex polygon, and (2) contain no other points of S interior to their convex hull. An &Ogr;( n 3 ) time and &Ogr;( n 2 ) space algorithm is introduced to find such subsets, where n represents the cardinality of S. Empirical results are obtained and presented. In particular, a configuration of 20 points is obtained with no empty convex hexagon, giving a partial answer to a question of Paul Erds.
computation point polygon convex hull timing space algorithm configurability