A new algorithm for shortest paths among obstacles in the plane
From MaRDI portal
Publication:1356167
DOI10.1007/BF01530888zbMath0875.68765MaRDI QIDQ1356167
Publication date: 7 July 1997
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (12)
Spatial Distribution of Traffic Flow in a Rectangular City with a Grid Network and a Rectangular Barrier ⋮ Routing in polygonal domains ⋮ Shortest paths in the plane with obstacle violations ⋮ Kinetic Geodesic Voronoi Diagrams in a Simple Polygon ⋮ Approximate Shortest Paths in Polygons with Violations ⋮ \(L_ 1\) shortest paths among polygonal obstacles in the plane ⋮ \(L_{1}\) cheapest paths in ``Fjord scenery ⋮ Time-minimal paths amidst moving obstacles in three dimensions ⋮ Unnamed Item ⋮ Quickest visibility queries in polygonal domains ⋮ Rectilinear paths among rectilinear obstacles ⋮ Routing in Polygonal Domains
Cites Work
- A note on two problems in connexion with graphs
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Visibility of disjoint polygons
- Time and space efficient algorithms for shortest paths between convex polygons
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- On the geodesic Voronoi diagram of point sites in a simple polygon
- An algorithmic approach to some problems in terrain navigation
- On the general motion-planning problem with two degrees of freedom
- The Discrete Geodesic Problem
- Euclidean shortest paths in the presence of rectilinear barriers
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Optimal Point Location in a Monotone Subdivision
- On Shortest Paths in Polyhedral Spaces
- Visibility graphs and obstacle-avoiding shortest paths
This page was built for publication: A new algorithm for shortest paths among obstacles in the plane
