k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON

DOI10.1142/S0218195999000315zbMath1074.68647OpenAlexW2104671918MaRDI QIDQ4682198

Evanthia Papadopoulou

Publication date: 10 June 2005

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195999000315

zbMATH Keywords

polygon decompositionsimple polygongeodesic triangulationaxis-parallel pathsNon-crossing paths

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (7)

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ The geodesic farthest-point Voronoi diagram in a simple polygon ⋮ Thick non-crossing paths in a polygonal domain

Cites Work

• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Maintenance of configurations in the plane
• Computing minimum length paths of a given homotopy class
• Ray shooting in polygons using geodesic triangulations
• Optimal shortest path queries in a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• Shortest Non-Crossing Rectilinear Paths in Plane Regions

This page was built for publication: k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON