Parallel methods for visibility and shortest-path problems in simple polygons
From MaRDI portal
Visibility problems for simple polygons are intensively studied in computational geometry, usually by means of visibility graphs and shortest-paths trees. The authors introduce a new data structure called stratified decomposition tree which allows to answer effectively shortes path queries in a simple polygon. This is a main tool for deriving a number of parallel algorithms, all running in \(O(\log n)\) time on CREW PRAM. This is an improvement over \(O(\log^ 2n)\) existing algorithms.
Recommendations
- Parallel algorithms for shortest path problems in polygons
- OPTIMAL MESH ALGORITHMS FOR PROXIMITY AND VISIBILITY PROBLEMS IN SIMPLE POLYGONS*
- An optimal parallel algorithm for the visibility of a simple polygon from a point
- Determining Weak Visibility of a Polygon from an Edge in Parallel
- AN OPTIMAL PARALLEL ALGORITHM FOR DETECTING WEAK VISIBILITY OF A SIMPLE POLYGON
Cites work
- A data structure for dynamic trees
- A linear algorithm for computing the visibility polygon from a point
- A simple parallel tree contraction algorithm
- Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
- An Efficient Parallel Biconnectivity Algorithm
- An optimal visibility graph algorithm for triangulated simple polygons
- Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
- Computing external farthest neighbors for a simple polygon
- Computing geodesic furthest neighbors in simple polygons
- Euclidean shortest paths in the presence of rectilinear barriers
- Finding the intersection of two convex polyhedra
- Finding the maximum, merging, and sorting in a parallel computation model
- Fractional cascading. I: A data structuring technique
- scientific article; zbMATH DE number 432842 (Why is no real title available?)
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 4064466 (Why is no real title available?)
- scientific article; zbMATH DE number 4064467 (Why is no real title available?)
- scientific article; zbMATH DE number 4064468 (Why is no real title available?)
- scientific article; zbMATH DE number 42967 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- Line-segment intersection reporting in parallel
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Maintenance of configurations in the plane
- Optimal shortest path queries in a simple polygon
- Parallel algorithms for shortest path problems in polygons
- Parallel computational geometry
- Parallel Prefix Computation
- Parallel triangulation of a polygon in two calls to the trapezoidal map
- Stabbing line segments
- Triangulating a polygon in parallel
- Triangulating a simple polygon
- Triangulating a simple polygon in linear time
- Visibility and intersection problems in plane geometry
Cited in
(11)- Solving visibility and separability problems on a mesh-of-processors
- Parallel algorithms for shortest path problems in polygons
- An addendum to parallel methods for visibility and shortest-path problems in simple polygons
- scientific article; zbMATH DE number 3866618 (Why is no real title available?)
- OPTIMAL MESH ALGORITHMS FOR PROXIMITY AND VISIBILITY PROBLEMS IN SIMPLE POLYGONS*
- Parallelizing an Algorithm for Visibility on Polyhedral Terrain
- Determining Weak Visibility of a Polygon from an Edge in Parallel
- AN OPTIMAL PARALLEL ALGORITHM FOR DETECTING WEAK VISIBILITY OF A SIMPLE POLYGON
- Scalable algorithms for bichromatic line segment intersection problems on Coarse Grained Multicomputers
- Minimizing Distance-to-Sight in Polygonal Domains
- scientific article; zbMATH DE number 278832 (Why is no real title available?)
This page was built for publication: Parallel methods for visibility and shortest-path problems in simple polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201749)
