Visibility graphs and obstacle-avoiding shortest paths

DOI10.1007/BF01928918MaRDI QIDQ3803163zbMATH OpenWikidataFDO

Authors Helmut Alt, Emo Welzl

Publication date 1988

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

zbMATH Keywords

computational geometryshortest pathsefficient algorithmsvisibility graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1182918
• Euclidean shortest paths in the presence of rectilinear barriers
• Shortest paths in the plane with convex polygonal obstacles
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• New results on shortest paths in three dimensions

Cites work

• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• An algorithm for shortest-path motion in three dimensions
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Euclidean shortest paths in the presence of rectilinear barriers
• On Shortest Paths in Polyhedral Spaces
• Shortest paths in the plane with convex polygonal obstacles
• The Discrete Geodesic Problem
• Topologically sweeping an arrangement
• Visibility of disjoint polygons

Cited in

(16)

• scientific article; zbMATH DE number 2087475 (Why is no real title available?)
• Supply facility and input/output point locations in the presence of barriers
• A maximum b-matching problem arising from median location models with applications to the roommates problem
• scientific article; zbMATH DE number 4062603 (Why is no real title available?)
• Crossing-Free Spanning Trees in Visibility Graphs of Points between Monotone Polygonal Obstacles
• A new algorithm for shortest paths among obstacles in the plane
• scientific article; zbMATH DE number 1919437 (Why is no real title available?)
• Maximising the worth of nascent networks
• Genetic algorithm for obstacle location-allocation problems with customer priorities
• A fast shortest path algorithm on terrain-like graphs
• Shortest polygonal paths in space
• A discrete mathematical model for the dynamics of a crowd of gazing pedestrians with and without an evolving environmental awareness
• Routing on the Visibility Graph
• Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs
• Fastest-path planning for direction-dependent speed functions
• Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3803163)