Parallel algorithms for shortest path problems in polygons
type: Item
instance of: scholarly article
title: Parallel algorithms for shortest path problems in polygons
zbMATH Open document ID: 0646.68058
DOI: 10.1007/BF01901194
author: Hossam ElGindy
author: Michael T. Goodrich
published in: The Visual Computer
publication date: 1988-01-01T00:00:00Z
review text: Given an n-vertex simple polygon \({\mathfrak P}\) we address the following problems: (i) find the shortest path between two points s and d inside \({\mathfrak P}\), and (ii) compute the shortest-path tree between a single point s and each vertex of \({\mathfrak P}\) (which implicitly represents all the shortest paths). We show how to solve the first problem in O(log n) time using O(n) processors, and the more general second problem in \(O(\log^ 2 n)\) time using O(n) processors for any simple polygon \({\mathfrak P}\). We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithms.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 52A10
zbMATH DE Number: 4055044
zbMATH Keywords: computational geometry
zbMATH Keywords: parallel algorithms
zbMATH Keywords: simple polygon
zbMATH Keywords: shortest- path tree
zbMATH Keywords: CREW RAM shared memory model of computation
MaRDI profile type: Publication
cites work: Q3942160
cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
cites work: Euclidean shortest paths in the presence of rectilinear barriers
cites work: Q3694703
cites work: Q3683547
cites work: A Systolic Design for Connectivity Problems
cites work: An Efficient Parallel Biconnectivity Algorithm
cites work: Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
full work available at URL: https://doi.org/10.1007/bf01901194
OpenAlex ID: W2052770190
Recommended article: Parallel methods for visibility and shortest-path problems in simple polygons
Recommended article: Efficient parallel algorithms for shortest paths in planar graphs
Recommended article: Optimal parallel algorithms for point-set and polygon problems
Recommended article: Q4511224
Recommended article: Q4005371
Recommended article: Efficient parallel algorithms for shortest paths in planar digraphs
Recommended article: An addendum to parallel methods for visibility and shortest-path problems in simple polygons
Recommended article: Parallel algorithms for geometric graph problems
Recommended article: A parallel shortest path algorithm
description: scientific article; zbMATH DE number 4055044