Computing minimum length paths of a given homotopy class
From MaRDI portal
Publication:1330462
DOI10.1016/0925-7721(94)90010-8zbMath0815.68116OpenAlexW2081751185WikidataQ56970846 ScholiaQ56970846MaRDI QIDQ1330462
J. E. Hershberger, Jack Scott Snoeyink
Publication date: 21 July 1994
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0925-7721(94)90010-8
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Homotopy theory (55P99)
Related Items
Structured discrete shape approximation: theoretical complexity and practical algorithm, Computing the Fréchet Distance Between Polygons with Holes, Median trajectories, AN OPTIMAL MORPHING BETWEEN POLYLINES, AN APPROXIMATE MORPHING BETWEEN POLYLINES, ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE, Shortest paths in the plane with obstacle violations, Computing \(L_1\) shortest paths among polygonal obstacles in the plane, Inserting Multiple Edges into a Planar Graph, Homotopic \(\mathcal{C}\)-oriented routing with few links and thick edges, Efficient observer-dependent simplification in polygonal domains, Shortest path planning for a tethered robot, Computing homotopic shortest paths efficiently, Shortest paths and convex hulls in 2D complexes with non-positive curvature, Geometric path problems with violations, Testing graph isotopy on surfaces, Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs, Minimum-link paths revisited, Approximate Shortest Paths in Polygons with Violations, Finding an approximate minimum-link visibility path inside a simple polygon, APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS, An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains, Computing the \(L_1\) geodesic diameter and center of a polygonal domain, A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation, Minimum weight connectivity augmentation for planar straight-line graphs, \(L_{1}\) shortest path queries in simple polygons, Computing pseudotriangulations via branched coverings, Unnamed Item, k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON, Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees, Unnamed Item, A fast shortest path algorithm on terrain-like graphs, Tracing compressed curves in triangulated surfaces, Fast optimal and bounded suboptimal Euclidean pathfinding, Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time, Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane, Typical representatives of free homotopy classes in multi-punctured plane, Rectilinear paths among rectilinear obstacles, Computing an \(L_1\) shortest path among splinegonal obstacles in the plane, A Census of Plane Graphs with Polyline Edges, \(L_1\) geodesic farthest neighbors in a simple polygon and related problems, GEODESIC-PRESERVING POLYGON SIMPLIFICATION, Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- The intersection searching problem for c-oriented polygons
- Finding minimal nested polygons
- On rectilinear link distance
- An optimal algorithm for computing a minimum nested nonconvex polygon
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Rectilinear shortest paths in the presence of rectangular barriers
- Triangulating a simple polygon in linear time
- Optimal computation of finitely oriented convex hulls
- Finding minimal convex nested polygons
- Optimal shortest path queries in a simple polygon
- On separating two simple polygons by a single translation
- An efficient algorithm for determining the convex hull of a finite planar set
- A linear time algorithm for minimum link paths inside a simple polygon
- An Introduction to the Geometry of Numbers
- Complexity of Single-Layer Routing
- Euclidean shortest paths in the presence of rectilinear barriers
- The Number of Shortest Paths on the Surface of a Polyhedron
- Optimal Placement for River Routing
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Triangulating Simple Polygons and Equivalent Problems
- On Shortest Paths in Polyhedral Spaces
- New algorithms for special cases of the hidden line elimination problem
- Finding minimum rectilinear distance paths in the presence of barriers
- An Output-Sensitive Algorithm for Computing Visibility Graphs
- Translating polygons with applications to hidden surface removal
- Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
- Computing the visibility polygon from a convex set and related problems
