Optimal time bounds for some proximity problems in the plane
Aggarwal, Alok
Herbert Edelsbrunner
Raghavan, Prabhakar
Tiwari, Prasoon
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.
Elsevier
1992
info:eu-repo/semantics/article
doc-type:article
text
https://research-explorer.app.ist.ac.at/record/4048
Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. Optimal time bounds for some proximity problems in the plane. <i>Information Processing Letters</i>. 1992;42(1):55-60. doi:<a href="https://doi.org/10.1016/0020-0190(92)90133-G">10.1016/0020-0190(92)90133-G</a>
info:eu-repo/semantics/altIdentifier/doi/10.1016/0020-0190(92)90133-G
info:eu-repo/semantics/closedAccess