10.1016/0020-0190(92)90133-G
Aggarwal, Alok
Alok
Aggarwal
Herbert Edelsbrunner
Herbert
Edelsbrunner0000-0002-9823-6833
Raghavan, Prabhakar
Prabhakar
Raghavan
Tiwari, Prasoon
Prasoon
Tiwari
Optimal time bounds for some proximity problems in the plane
Elsevier
1992
2018-12-11T12:06:38Z
2019-04-26T07:22:39Z
journal_article
https://research-explorer.app.ist.ac.at/record/4048
https://research-explorer.app.ist.ac.at/record/4048.json
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.