---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: David
foaf_name: Dobkin, David
foaf_surname: Dobkin
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Edelsbrunner, Herbert
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Mark
foaf_name: Overmars, Mark
foaf_surname: Overmars
bibo_doi: 10.1007/BF01840404
bibo_issue: '4'
bibo_volume: 5
dct_date: 1990^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0178-4617
- http://id.crossref.org/issn/1432-0541
dct_language: eng
dct_publisher: Springer@
dct_title: Searching for empty convex polygons@
...