Accession Number : ADA297036

Title :   Proximity Problems for Points on a Rectilinear Plane with Rectangular Obstacles,

Corporate Author : WISCONSIN UNIV-MILWAUKEE DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Personal Author(s) : Guha, Sumanta ; Suzuki, Ichiro

PDF Url : ADA297036

Report Date : 1994

Pagination or Media Count : 26

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)

Descriptors :   *ALGORITHMS, *PLANE GEOMETRY, OPTIMIZATION, COMPUTATIONS, RECTANGULAR BODIES, BARRIERS, SEQUENCES(MATHEMATICS), POLYGONS, POINTS(MATHEMATICS).

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE