Closest-Point Queries for Complex Objects

摘要

In this paper we report on the implementation of a heuristic for preprocessing a set of n points in the plane to find one that is closest to the boundary of an object that is geometrically more complex than a simple point, to wit, a line, a half-line, a line-segment, a rectangle, a convex polygon with a fixed number of sides, a circle, an ellipse, or any other convex object whose boundary has a constant-sized description. Our experimental results show that the heuristic is more effective than a naive brute-force approach for query objects with small perimeter relative to the given point set, and large values of n.