Optimal time bounds for some proximity problems in the plane (Q1198024)

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.