A plane-sweep algorithm for the all-nearest neighbors problem for a set of convex planar objects

Graf T, Hinrichs KH

Abstract

We present a plane-sweep algorithm that solves the all - nearest - neighbors problem with respect to an arbitrary Minkowski-metric d t (1 ≤ t ≤ ∞) for a set of non-intersecting planar compact convex objects, such as points, line segments, circular arcs and convex polygons. The algorithm also applies if we replace the condition of disjointness by the weaker condition that the objects in the configuration are diagonal-disjoint. For configurations of points, line segments or disks the algorithm runs in asymptotically optimal tune O(n log n). For a configuration of n convex polygons with a total of N edges it finds nearest neighbors with respect to the Euclidean L 2-metric in time O(n log N) if each polygon is given by its vertices in cyclic order.