Link distance and shortest path problems in the plane

DOI10.1016/j.comgeo.2011.04.004zbMath1262.65029MaRDI QIDQ634253

Carola Wenk, Atlas F. IV. Cook

Publication date: 2 August 2011

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2011.04.004

zbMATH Keywords

shortest paths; polygonal domain; computational geometry; Voronoi diagrams; Hausdorff distance; Fréchet distance; link distance; simple polygon

Mathematics Subject Classification ID

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parametric search made practical
• Abstract Voronoi diagrams revisited
• Guarding galleries and terrains
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Computing the full visibility graph of a set of line segments
• Minimum-link paths among obstacles in the plane
• New similarity measures between polylines with applications to morphing and polygon sweeping
• Comparison of distance measures for planar curves
• A linear time algorithm for minimum link paths inside a simple polygon
• Walking your dog in the woods in polynomial time
• Link Distance and Shortest Path Problems in the Plane
• Querying Two Boundary Points for Shortest Paths in a Polygonal Domain
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Path Planning in 0/1/∞ Weighted Regions with Applications
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Slowing down sorting networks to obtain faster sorting algorithms
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Fréchet Distance for Curves, Revisited
• Faster shortest-path algorithms for planar graphs