Proximity Problems for Points on a Rectilinear Plane with Rectangular Obstacles,
Abstract
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 closet 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 u) 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 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. (AN)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1994
- Accession Number
- ADA297036
Entities
People
- Ichiro Suzuki
- Sumanta Guha
Organizations
- University of Wisconsin–Milwaukee