Searching for empty convex polygons

ABSTRACT

A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r > 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.

REFERENCES

• 1: David Avis , David Rappaport, Computing the largest empty convex subset of a set of points, Proceedings of the first annual symposium on Computational geometry, p.161-167, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323255]
• 2: B~r~nyi, I. and Fiiredi, Z., Empty simplices in Euclidean space, Rep. 689, School Oper. Res. industr. Engin., Cornel} Univ., Ithaca, NY, 1987.
• 3: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 4: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• 5: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 6: Erd~s~ P., Combinatorial problems in geometry and number theory, Proe. Sympos. Pure Math. 34 (1979), 149-162.
• 7: Harborth, H., Konvex Fiinfecke in ebenen Punktmengen, Elem. Math. 33 (1978), 116-118.
• 8: J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size, Proceedings of the third annual symposium on Computational geometry, p.11-20, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41960]
• 9: Horton, J.D., Sets with no empty convex 7-gons, Canad. Math. Bull. 26 (1983), 482-484.
• 10: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 11: Overmars, M.H., Scholten, B. and Vincent, I., Sets without empty convex 6-gons, Rep., Dept. Comput. Sci., Univ. Utrecht, the Netherlands, 1988.

INDEX TERMS

Primary 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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Measurement, Performance, Theory