Searching for empty convex polygons

David P. Dobkin, Herbert Edelsbrunner, Mark H. Overmars

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
PublisherAssociation for Computing Machinery, Inc
Pages224-228
Number of pages5
ISBN (Electronic)0897912705, 9780897912709
DOIs
StatePublished - Jan 6 1988
Event4th Annual Symposium on Computational Geometry, SCG 1988 - Urbana-Champaign, United States
Duration: Jun 6 1988Jun 8 1988

Publication series

NameProceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

Other

Other4th Annual Symposium on Computational Geometry, SCG 1988
CountryUnited States
CityUrbana-Champaign
Period6/6/886/8/88

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Searching for empty convex polygons'. Together they form a unique fingerprint.

  • Cite this

    Dobkin, D. P., Edelsbrunner, H., & Overmars, M. H. (1988). Searching for empty convex polygons. In Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988 (pp. 224-228). (Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988). Association for Computing Machinery, Inc. https://doi.org/10.1145/73393.73416