---
res:
bibo_abstract:
- 'Given a sequence of n points that form the vertices of a simple polygon, we show
that determining a closest pair requires OMEGA(n log n) time in the algebraic
decision tree model. Together with the well-known O(n log n) upper bound for finding
a closest pair, this settles an open problem of Lee and Preparata. We also extend
this O(n log n) upper bound to the following problem: Given a collection of sets
with a total of n points in the plane, find for each point a closest neighbor
that does not belong to the same set.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Alok
foaf_name: Aggarwal, Alok
foaf_surname: Aggarwal
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Prabhakar
foaf_name: Raghavan, Prabhakar
foaf_surname: Raghavan
- foaf_Person:
foaf_givenName: Prasoon
foaf_name: Tiwari, Prasoon
foaf_surname: Tiwari
bibo_doi: 10.1016/0020-0190(92)90133-G
bibo_issue: '1'
bibo_volume: 42
dct_date: 1992^xs_gYear
dct_publisher: Elsevier@
dct_title: Optimal time bounds for some proximity problems in the plane@
...