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
    0 references
    0 references
    0 references
    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
    0 references
    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
    0 references