Computing the largest empty convex subset of a set of points

ABSTRACT

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;(n3) time and &Ogr;(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.

REFERENCES

• 1: [1] V. Chvátal, G. Klincsek, Finding Largest Convex Subsets, Congresus Numeratlum, Vol. 29 (1980) pp. 453-460.
• 2: [2] H. El-Gindy, D. Avis, A Linear Algorithm for Computing the Visibility Polygon from a Point, J. Algorithms 2(June 1981) pp. 186-197.
• 3: [3] P. Erdös, G. Szekeres A Combinatorial Problem in Geometry, Compositio Math. 2 (1935) pp. 463-470. (Also appears in [5]).
• 4: [4] P. Erdös, G. Szekeres On Some Extremum Problems in Elementary Geometry Ann. Univ Sci. Budapest 3-4 (1960/1) PP. 53-62. (Also appears in [5]).
• 5: [5] P. Erdös, Paul Erdös: The Art of Counting M.I.T. Press, Ed. J.H. Spencer, 1973.
• 6: [6] J.E. Goodman, R. Pollack, Geometric Sorting, New York Academy of Sciences, Annals of Discrete Geometry and Convexity (1982).
• 7: [7] H. Harborth, Konvex Funfecke in ebenen Punkmengen , Elem. Math. 33 (1978) 116-118.
• 8: [8] J. D. Horton, Sets with no Empty Convex 7-gons, C. Math. Bull. 26 (Dec. 1983) 482-484.
• 9: [9] W. Moser, Research Problems in Discrete Geometry, Department of Mathematics, McGill University, (1981) (problem 29).
• 10: [10] D. Rappaport, G. T. Toussaint, A Simple Linear Hidden-Line Algorithm for Star-Shaped Polygons, McGill University Tech. Report no. SOCS 83.23, November 1983. (To appear in Pattern Recognition Letters.)
• 11: [11] M.I. Shamos, Problems in Computational Geometry, Carnegie Melon University, 1977.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification