Optimal time bounds for some proximity problems in the plane
Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. 1992. Optimal time bounds for some proximity problems in the plane. Information Processing Letters. 42(1), 55–60.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Aggarwal, Alok;
Edelsbrunner, HerbertISTA 
;
Raghavan, Prabhakar;
Tiwari, Prasoon
;
Raghavan, Prabhakar;
Tiwari, PrasoonAbstract
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.
Publishing Year
Date Published
1992-04-27
Journal Title
Information Processing Letters
Publisher
Elsevier
Acknowledgement
Research supported by the National Science Foundation under Grant CCR-8714565.
Volume
42
Issue
1
Page
55 - 60
ISSN
eISSN
IST-REx-ID
Cite this
Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. Optimal time bounds for some proximity problems in the plane. Information Processing Letters. 1992;42(1):55-60. doi:10.1016/0020-0190(92)90133-G
Aggarwal, A., Edelsbrunner, H., Raghavan, P., & Tiwari, P. (1992). Optimal time bounds for some proximity problems in the plane. Information Processing Letters. Elsevier. https://doi.org/10.1016/0020-0190(92)90133-G
Aggarwal, Alok, Herbert Edelsbrunner, Prabhakar Raghavan, and Prasoon Tiwari. “Optimal Time Bounds for Some Proximity Problems in the Plane.” Information Processing Letters. Elsevier, 1992. https://doi.org/10.1016/0020-0190(92)90133-G.
A. Aggarwal, H. Edelsbrunner, P. Raghavan, and P. Tiwari, “Optimal time bounds for some proximity problems in the plane,” Information Processing Letters, vol. 42, no. 1. Elsevier, pp. 55–60, 1992.
Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. 1992. Optimal time bounds for some proximity problems in the plane. Information Processing Letters. 42(1), 55–60.
Aggarwal, Alok, et al. “Optimal Time Bounds for Some Proximity Problems in the Plane.” Information Processing Letters, vol. 42, no. 1, Elsevier, 1992, pp. 55–60, doi:10.1016/0020-0190(92)90133-G.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar