Computing homotopic shortest paths in the plane

DOI10.1016/S0196-6774(03)00090-7zbMath1060.68147MaRDI QIDQ4458869

Sergei Bespamyatnikh

Publication date: 14 March 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

Shortest pathHomotopyOutput-sensitive algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (11)

Alternating paths along axis-parallel segments ⋮ Homotopic \(\mathcal{C}\)-oriented routing with few links and thick edges ⋮ Shortest path planning for a tethered robot ⋮ Computing homotopic shortest paths efficiently ⋮ Testing graph isotopy on surfaces ⋮ Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs ⋮ APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS ⋮ Computing homotopic line simplification ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ Typical representatives of free homotopy classes in multi-punctured plane ⋮ A Census of Plane Graphs with Polyline Edges

This page was built for publication: Computing homotopic shortest paths in the plane