Optimal time bounds for some proximity problems in the plane

A. Aggarwal, H. Edelsbrunner, P. Raghavan, P. Tiwari, Information Processing Letters 42 (1992) 55–60.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ;
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.
Publishing Year
Date Published
1992-04-27
Journal Title
Information Processing Letters
Volume
42
Issue
1
Page
55 - 60
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, 42(1), 55–60. 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 42, no. 1 (1992): 55–60. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar