L₁ shortest path queries among polygonal obstacles in the plane

DOI10.4230/LIPICS.STACS.2013.293zbMATH Open1354.68275MaRDI QIDQ2957892FDOQ2957892

Authors Danny Z. Chen, Haitao Wang 

Publication date 30 January 2017

Full work available at URL https://arxiv.org/abs/1202.5715

zbMATH Keywords

computational geometryshortest path queries\(L_1\)/\(L_\infty\)/rectilinear metricgeodesic Voronoi diagramsshortest path mapsshortest paths among obstacles

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• Two-point \(L_1\) shortest path queries in the plane
• Two-point \(L_1\) shortest path queries 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

Cited In (17)

• Planar spanners and approximate shortest path queries among obstacles in the plane
• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• ON GEOMETRIC PATH QUERY PROBLEMS
• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains
• Shadoks Approach to Low-Makespan Coordinated Motion Planning
• The Length of Shortest Vertex Paths in Binary Occupancy Grids Compared to Shortest r-Constrained Ones
• Two-point \(L_1\) shortest path queries in the plane
• Minimum-link shortest paths for polygons amidst rectilinear obstacles
• Quickest visibility queries in polygonal domains
• Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
• Two-point \(L_1\) shortest path queries in the plane
• \(L_{1}\) shortest path queries in simple polygons
• Shortest paths in the plane with convex polygonal obstacles
• On geometric path query problems
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain

This page was built for publication: \(L_1\) shortest path queries 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 Q2957892)