ISSN:
1432-0541
Keywords:
Computational geometry
;
Algorithms and data structures
;
Parallel computation
;
Link distance
;
Rectilinear polygons
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). LetP be a trapezoided rectilinear simple polygon withn vertices. InO(logn) time usingO(n/logn) processors we can optimally compute: 1. Minimum réctilinear link paths, or shortest paths in theL 1 metric from any point inP to all vertices ofP. 2. Minimum rectilinear link paths from any segment insideP to all vertices ofP. 3. The rectilinear window (histogram) partition ofP. 4. Both covering radii and vertex intervals for any diagonal ofP. 5. A data structure to support rectilinear link-distance queries between any two points inP (queries can be answered optimally inO(logn) time by uniprocessor). Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequential algorithm for this problem which usedO(n logn) time and space.5 We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01206332
Permalink
