Name
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. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1016/0020-0190(92)90133-G | Inf. Process. Lett. |
Keywords | Field | DocType |
optimal time bound,proximity problem,upper and lower bounds,euclidean distance,computational geometry | Discrete mathematics,Combinatorics,Polygon,Open problem,Vertex (geometry),Upper and lower bounds,Simple polygon,Time complexity,Mathematics,Closest pair of points problem,Proximity problems | Journal |
Volume | Issue | ISSN |
42 | 1 | 0020-0190 |
Citations | PageRank | References |
12 | 1.08 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alok Aggarwal | 1 | 1890 | 228.97 |
| Herbert Edelsbrunner | 2 | 6787 | 1112.29 |
| Prabhakar Raghavan | 3 | 13351 | 2776.61 |
| Prasoon Tiwari | 4 | 592 | 96.81 |