Searching for empty convex polygons
Dobkin, David
Edelsbrunner, Herbert
Overmars, Mark
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.
Springer
1990
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/4075
Dobkin D, Edelsbrunner H, Overmars M. Searching for empty convex polygons. <i>Algorithmica</i>. 1990;5(4):561-571. doi:<a href="https://doi.org/10.1007/BF01840404">10.1007/BF01840404</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/BF01840404
info:eu-repo/semantics/altIdentifier/issn/0178-4617
info:eu-repo/semantics/altIdentifier/issn/1432-0541
info:eu-repo/semantics/closedAccess