Parallel algorithms for shortest path problems in polygons
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.
- Parallel methods for visibility and shortest-path problems in simple polygons
- Efficient parallel algorithms for shortest paths in planar graphs
- Optimal parallel algorithms for point-set and polygon problems
- scientific article; zbMATH DE number 1522928
- scientific article; zbMATH DE number 56471
- Efficient parallel algorithms for shortest paths in planar digraphs
- An addendum to parallel methods for visibility and shortest-path problems in simple polygons
- Parallel algorithms for geometric graph problems
- A parallel shortest path algorithm
- A Systolic Design for Connectivity Problems
- An Efficient Parallel Biconnectivity Algorithm
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Euclidean shortest paths in the presence of rectilinear barriers
- scientific article; zbMATH DE number 3905859 (Why is no real title available?)
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- scientific article; zbMATH DE number 3759279 (Why is no real title available?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Parallel rectilinear shortest paths with rectangular obstacles
- Parallel methods for visibility and shortest-path problems in simple polygons
- Parallel mesh algorithms for grid graph shortest paths with application to separation of touching chromosomes
- Efficient piecewise-linear function approximation using the uniform metric
- Accelerated parallel projection method for solving the shortest distance problem
- PARALLEL COMPUTATION OF INTERNAL AND EXTERNAL FARTHEST NEIGHBORS IN SIMPLE POLYGONS
- OPTIMAL MESH ALGORITHMS FOR PROXIMITY AND VISIBILITY PROBLEMS IN SIMPLE POLYGONS*
- scientific article; zbMATH DE number 1522928 (Why is no real title available?)
- Determining Weak Visibility of a Polygon from an Edge in Parallel
- -Algorithms for Minimum Link Path and Related Problems
- scientific article; zbMATH DE number 278832 (Why is no real title available?)
This page was built for publication: Parallel algorithms for shortest path problems in polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104089)
