
Accession Number : ADA297036
Title : Proximity Problems for Points on a Rectilinear Plane with Rectangular Obstacles,
Corporate Author : WISCONSIN UNIVMILWAUKEE 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 planesweep, and the consideration of geometrically special types of shortest paths, socalled zfirst paths. For (c) we present an O((n + k) log(n + k) log u) time sequential algorithm that implements a sophisticated divideandconquer scheme with an added extension phase. In the extension phase of this scheme we introduce novel geometric structures, in particular socalled zdiagrams, 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 nearoptimal, 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