Computing \(L_1\) shortest paths among polygonal obstacles in the plane
From MaRDI portal
Publication:2414865
DOI10.1007/s00453-018-00540-xzbMath1421.68164OpenAlexW2963551506MaRDI QIDQ2414865
Publication date: 17 May 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-00540-x
algorithmsdata structuresshortest pathscomputational geometryVoronoi diagramspolygonal domainsL1 metric
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items
Cites Work
- Unnamed Item
- Planar rectilinear shortest path computation using corridors
- Visibility and intersection problems in plane geometry
- Shortest paths in the plane with convex polygonal obstacles
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Corrections to Lee's visibility polygon algorithm
- Rectilinear shortest paths in the presence of rectangular barriers
- Triangulating a simple polygon in linear time
- On graphs preserving rectilinear shortest paths in the presence of obstacles
- \(L_ 1\) shortest paths among polygonal obstacles in the plane
- Computing minimum length paths of a given homotopy class
- Ray shooting in polygons using geodesic triangulations
- An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
- A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains
- Computing the Visibility Polygon of an Island in a Polygonal Domain
- Computing Shortest Paths amid Convex Pseudodisks
- Two-point L1 shortest path queries in the plane
- On Some Distance Problems in Fixed Orientations
- Visibility of a simple polygon
- Fast triangulation of the plane with respect to simple polygons
- Optimal Point Location in a Monotone Subdivision
- Finding minimum rectilinear distance paths in the presence of barriers
- Optimal Search in Planar Subdivisions
- An Output-Sensitive Algorithm for Computing Visibility Graphs
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- An optimal parallel algorithm for the visibility of a simple polygon from a point
- Shortest paths in the plane with polygonal obstacles
- TRIANGULATING DISJOINT JORDAN CHAINS
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
- Computing Shortest Paths among Curved Obstacles in the Plane
- SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
