Computing L₁ shortest paths among polygonal obstacles in the plane
DOI10.1007/S00453-018-00540-XzbMATH Open1421.68164OpenAlexW2963551506MaRDI QIDQ2414865FDOQ2414865
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
Recommendations
- \(L_1\) shortest path queries among polygonal obstacles in the plane
- A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
- \(L_ 1\) shortest paths among polygonal obstacles in the plane
- SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
- Two-point \(L_1\) shortest path queries in the plane
algorithmscomputational geometrydata structuresshortest pathsVoronoi diagramspolygonal domainsL1 metric
Analysis of algorithms (68W40) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- \(L_ 1\) shortest paths among polygonal obstacles in the plane
- Triangulating a simple polygon in linear time
- Optimal Search in Planar Subdivisions
- An Output-Sensitive Algorithm for Computing Visibility Graphs
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- On graphs preserving rectilinear shortest paths in the presence of obstacles
- An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
- Optimal Point Location in a Monotone Subdivision
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
- Visibility and intersection problems in plane geometry
- Finding minimum rectilinear distance paths in the presence of barriers
- On Some Distance Problems in Fixed Orientations
- Corrections to Lee's visibility polygon algorithm
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- Ray shooting in polygons using geodesic triangulations
- Planar rectilinear shortest path computation using corridors
- Shortest paths in the plane with convex polygonal obstacles
- Visibility of a simple polygon
- An optimal parallel algorithm for the visibility of a simple polygon from a point
- Computing minimum length paths of a given homotopy class
- 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
- TRIANGULATING DISJOINT JORDAN CHAINS
- Shortest paths in the plane with polygonal obstacles
- Rectilinear shortest paths in the presence of rectangular barriers
- Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
- Fast triangulation of the plane with respect to simple polygons
- Computing shortest paths amid convex pseudodisks
- Title not available (Why is that?)
- Two-point L1 shortest path queries in the plane
- Computing Shortest Paths among Curved Obstacles in the Plane
Cited In (11)
- Title not available (Why is that?)
- Routing among convex polygonal obstacles in the plane
- Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
- \(L_{1}\) cheapest paths in ``Fjord scenery
- The shortest path AMID 3-D polyhedral obstacles
- Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
- The Length of Shortest Vertex Paths in Binary Occupancy Grids Compared to Shortest r-Constrained Ones
- Removing Connected Obstacles in the Plane is FPT
- The shortest path in a simple polygon with obstacles
- An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
- Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
This page was built for publication: Computing \(L_1\) shortest paths among polygonal obstacles in the plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414865)
