Optimal time bounds for some proximity problems in the plane (Q1198024)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal time bounds for some proximity problems in the plane |
scientific article |
Statements
Optimal time bounds for some proximity problems in the plane (English)
0 references
16 January 1993
0 references
The \(\Omega(n\log n)\)-time lower bound (under algebraic decision tree computation model) for the problem of finding the closest pair for the sequence of vertices of a monotone or star-shaped polygon is proven. This matches with the known upper bound for simple polygons. The proof is by reduction from the integer element uniqueness problem. Another main result is the \(0(n\log n)\) algorithm for the following closeness problem. Given a collection of point sets with \(n\) points in total, for each point find the closest one but not from the same set. Additionally, a simple \(0(n)\) algorithm is presented for the element uniqueness problem under the RAM model, to demonstrate its difference from the ADT model.
0 references
proximity
0 references
lower bound
0 references
closest pair
0 references
polygon
0 references
integer element uniqueness problem
0 references
point sets
0 references