Visibility graphs and obstacle-avoiding shortest paths

DOI10.1007/BF01928918zbMath0656.05062WikidataQ54309800 ScholiaQ54309800MaRDI QIDQ3803163

Helmut Alt, Ermo Welzl

Publication date: 1988

Published in: Zeitschrift für Operations Research (Search for Journal in Brave)

zbMATH Keywords

shortest pathscomputational geometryefficient algorithmsvisibility graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph theory (05C99)

Related Items (9)

Maximising the worth of nascent networks ⋮ A new algorithm for shortest paths among obstacles in the plane ⋮ A discrete mathematical model for the dynamics of a crowd of gazing pedestrians with and without an evolving environmental awareness ⋮ Fastest-path planning for direction-dependent speed functions ⋮ A maximum \(b\)-matching problem arising from median location models with applications to the roommates problem ⋮ Genetic algorithm for obstacle location-allocation problems with customer priorities ⋮ Supply facility and input/output point locations in the presence of barriers ⋮ Shortest polygonal paths in space ⋮ Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• An algorithm for shortest-path motion in three dimensions
• Shortest paths in the plane with convex polygonal obstacles
• Visibility of disjoint polygons
• Topologically sweeping an arrangement
• The Discrete Geodesic Problem
• Euclidean shortest paths in the presence of rectilinear barriers
• On Shortest Paths in Polyhedral Spaces

This page was built for publication: Visibility graphs and obstacle-avoiding shortest paths