Computing the largest empty convex subset of a set of points
David Avis, David D. Rappaport · 1985
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 Ο(n3) time and Ο(n2) 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 Erdös.