@inproceedings{7c39b45e61254f9d8f021c864fa2cfab,

title = "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.",

author = "Dobkin, {David P.} and Herbert Edelsbrunner and Overmars, {Mark H.}",

note = "Funding Information: XThe first author is pleased to acknowledge support by the National Sci-erce Foundation under grant CCR-8700917. Research of the second author was supported by Amoco Foundation Faculty Development Grant CS 1--6-44862 and by the National Selence Foundation under grant CCR-8714565. Publisher Copyright: {\textcopyright} 1988 ACM.; 4th Annual Symposium on Computational Geometry, SCG 1988 ; Conference date: 06-06-1988 Through 08-06-1988",

year = "1988",

month = jan,

day = "6",

doi = "10.1145/73393.73416",

language = "English (US)",

series = "Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988",

publisher = "Association for Computing Machinery, Inc",

pages = "224--228",

booktitle = "Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988",

}