Proximity Problems and the Voronoi Diagram on a Rectilinear Plane withRectangular Obstacles

摘要

We consider the following four problems for a set S of K points on a plane,equipped with the rectilinear metric and containing a set R of n disjoint rectangular obstacles (so that distance is measured by a shortest rectilinear path avoiding obstacles in R): (a) find a closest pair of points in S, (b) find a nearest neighbor for each point in S, (c) compute the rectilinear Voronoi diagram of S, and (d) compute a rectilinear minimal spanning tree of S. We describe O((n + k) log(n + k)) time sequential algorithms for (a) and (b) based on plane-sweep, and the consideration of geometrically special types of shortest paths, so-called z-first paths. For (c) we present an O((n + k) log(n + k) log n) time sequential algorithm that implements a sophisticated divide-and-conquer scheme with an added extension phase. In the extension phase of this scheme we introduce introduce novel geometric structures, in particular so-called z-diagrams, and techniques associated with the Voronoi diagram. Problem (d) can be reduced to (c) and solved in O(((n + k) log(n + k) log n) time as well. All our algorithms are near-optimal, as well as easy to implement.