Searching for empty convex polygons

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

Research output: Contribution to journalArticle

20 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)
Pages (from-to)561-571
Number of pages11
JournalAlgorithmica
Volume5
Issue number1
DOIs
StatePublished - Mar 1990

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Analysis of algorithms
  • Combinatorial geometry
  • Computational geometry
  • Empty convex subsets

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. (1990). Searching for empty convex polygons. Algorithmica, 5(1), 561-571. https://doi.org/10.1007/BF01840404