Searching for empty convex polygons

D. Dobkin, H. Edelsbrunner, M. Overmars, Algorithmica 5 (1990) 561–571.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
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.
Publishing Year
Date Published
1990-01-01
Journal Title
Algorithmica
Acknowledgement
The first author is pleased to acknowledge support by the National Science Foundation under Grant CCR-8700917. The research of the second author was supported by Amoco Foundation Faculty Development Grant CS 1-6-44862 and by the National Science Foundatio
Volume
5
Issue
4
Page
561 - 571
IST-REx-ID

Cite this

Dobkin D, Edelsbrunner H, Overmars M. Searching for empty convex polygons. Algorithmica. 1990;5(4):561-571. doi:10.1007/BF01840404
Dobkin, D., Edelsbrunner, H., & Overmars, M. (1990). Searching for empty convex polygons. Algorithmica, 5(4), 561–571. https://doi.org/10.1007/BF01840404
Dobkin, David, Herbert Edelsbrunner, and Mark Overmars. “Searching for Empty Convex Polygons.” Algorithmica 5, no. 4 (1990): 561–71. https://doi.org/10.1007/BF01840404.
D. Dobkin, H. Edelsbrunner, and M. Overmars, “Searching for empty convex polygons,” Algorithmica, vol. 5, no. 4, pp. 561–571, 1990.
Dobkin D, Edelsbrunner H, Overmars M. 1990. Searching for empty convex polygons. Algorithmica. 5(4), 561–571.
Dobkin, David, et al. “Searching for Empty Convex Polygons.” Algorithmica, vol. 5, no. 4, Springer, 1990, pp. 561–71, doi:10.1007/BF01840404.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar