Computing minimum length paths of a given homotopy class
From MaRDI portal
It is shown how the notion of the universal covering space of a triangulated region can be used as a unifying framework to compute paths under various metrics in a simple polygon. Shortest paths and shortest closed curves under Euclidean and link metrics and paths that are restricted to use \(c\) given orientations are considered and new algorithms for computing minimum length and minimum link \(c\)-oriented paths are given. Also algorithms using simple arrays and stacks instead of more complicated data structures used in previously known algorithms for Euclidean shortest path trees and minimum-link paths are given.
Recommendations
Cites work
- A linear time algorithm for minimum link paths inside a simple polygon
- A note on two problems in connexion with graphs
- An efficient algorithm for determining the convex hull of a finite planar set
- An Introduction to the Geometry of Numbers
- An optimal algorithm for computing a minimum nested nonconvex polygon
- An Output-Sensitive Algorithm for Computing Visibility Graphs
- Complexity of Single-Layer Routing
- Computing the visibility polygon from a convex set and related problems
- Elementary differential geometry
- Euclidean shortest paths in the presence of rectilinear barriers
- Finding minimal convex nested polygons
- Finding minimal nested polygons
- Finding minimum rectilinear distance paths in the presence of barriers
- Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
- scientific article; zbMATH DE number 432849 (Why is no real title available?)
- scientific article; zbMATH DE number 3945379 (Why is no real title available?)
- scientific article; zbMATH DE number 3680756 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3479762 (Why is no real title available?)
- scientific article; zbMATH DE number 3562121 (Why is no real title available?)
- scientific article; zbMATH DE number 1256695 (Why is no real title available?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- New algorithms for special cases of the hidden line elimination problem
- On rectilinear link distance
- On separating two simple polygons by a single translation
- On Shortest Paths in Polyhedral Spaces
- Optimal computation of finitely oriented convex hulls
- Optimal Placement for River Routing
- Optimal shortest path queries in a simple polygon
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Rectilinear shortest paths in the presence of rectangular barriers
- The intersection searching problem for c-oriented polygons
- The Number of Shortest Paths on the Surface of a Polyhedron
- Translating polygons with applications to hidden surface removal
- Triangulating a simple polygon in linear time
- Triangulating Simple Polygons and Equivalent Problems
Cited in
(49)- Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
- Homotopic \(\mathcal{C}\)-oriented routing with few links and thick edges
- Geometric path problems with violations
- Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
- A fast shortest path algorithm on terrain-like graphs
- Fast optimal and bounded suboptimal Euclidean pathfinding
- Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
- Shortest paths in the plane with obstacle violations
- Shortest paths and convex hulls in 2D complexes with non-positive curvature
- Minimum weight connectivity augmentation for planar straight-line graphs
- \(L_{1}\) shortest path queries in simple polygons
- Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
- \(L_1\) geodesic farthest neighbors in a simple polygon and related problems
- Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
- Median trajectories
- Computing \(L_1\) shortest paths among polygonal obstacles in the plane
- Efficient observer-dependent simplification in polygonal domains
- Computing homotopic shortest paths efficiently
- Testing graph isotopy on surfaces
- Minimum-link paths revisited
- A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
- Rectilinear paths among rectilinear obstacles
- ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
- Minimum weight connectivity augmentation for planar straight-line graphs
- Computing the Fréchet distance between polygons with holes
- scientific article; zbMATH DE number 177559 (Why is no real title available?)
- Computing homotopic shortest paths in the plane
- APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS
- k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
- AN OPTIMAL MORPHING BETWEEN POLYLINES
- A divide-and-conquer algorithm for two-point L₁ shortest path queries in polygonal domains
- Shortest paths in the plane with obstacle violations
- Approximate Shortest Paths in Polygons with Violations
- Typical representatives of free homotopy classes in multi-punctured plane
- Geodesic-preserving polygon simplification
- A Census of Plane Graphs with Polyline Edges
- Computing the \(L_1\) geodesic diameter and center of a polygonal domain
- AN APPROXIMATE MORPHING BETWEEN POLYLINES
- Tracing compressed curves in triangulated surfaces
- Inserting Multiple Edges into a Planar Graph
- k-pairs non-crossing shortest paths in a simple polygon
- Finding an approximate minimum-link visibility path inside a simple polygon
- Towards space efficient two-point shortest path queries in a polygonal domain
- A new algorithm for Euclidean shortest paths in the plane
- Computing pseudotriangulations via branched coverings
- Link diameter, radius and 2-point link distance queries in polygonal domains
- Towards space efficient two-point shortest path queries in a polygonal domain
- Structured discrete shape approximation: theoretical complexity and practical algorithm
- Shortest path planning for a tethered robot
This page was built for publication: Computing minimum length paths of a given homotopy class
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1330462)
