Parallel methods for visibility and shortest-path problems in simple polygons |
| |
Authors: | Michael T Goodrich Steven B Shauck and Sumanta Guha |
| |
Affiliation: | (1) Department of Computer Science, Johns Hopkins University, 21218 Baltimore, MD, USA;(2) Westinghouse Electric Corporation, M/S 463, P.O. Box 746, 21203 Baltimore, MD, USA;(3) Department of Electrical Engineering and Computer Science, University of Wisconsin at Milwaukee, 53201 Milwaukee, WI, USA |
| |
Abstract: | In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.This research was announced in preliminary form in theProceedings of the 6th ACM Symposium on Computational Geometry, 1990, pp. 73–82. The research of Michael T. Goodrich was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092. |
| |
Keywords: | Parallel algorithms Computational geometry Data structures Visibility Polygons CREW PRAM |
本文献已被 SpringerLink 等数据库收录! |
|