A divide-and-conquer algorithm for two-point L₁ shortest path queries in polygonal domains

DOI10.4230/LIPICS.SOCG.2019.59MaRDI QIDQ5088992FDOQ5088992

Authors: Haitao Wang 

Publication date: 18 July 2022

Recommendations

• A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains
• \(L_{1}\) shortest path queries in simple polygons
• Two-point \(L_1\) shortest path queries in the plane
• Two-point \(L_1\) shortest path queries in the plane
• \(L_1\) shortest path queries among polygonal obstacles in the plane

zbMATH Keywords

shortest pathspolygonal domains\(L_1\) metrictwo-point queries

Mathematics Subject Classification ID

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
• Geometric applications of a matrix-searching algorithm
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Optimal shortest path queries in a simple polygon
• Shortest Path Queries in Polygonal Domains
• Title not available (Why is that?)
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Planar rectilinear shortest path computation using corridors
• Computing minimum length paths of a given homotopy class
• TRIANGULATING DISJOINT JORDAN CHAINS
• ON GEOMETRIC PATH QUERY PROBLEMS
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
• Better tradeoffs for exact distance oracles in planar graphs
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• A new data structure for shortest path queries in a simple polygon
• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• Shortest path queries in planar graphs
• Exact distance oracles for planar graphs
• Two-point \(L_1\) shortest path queries in the plane

Cited In (2)

• Shortest rectilinear path queries to rectangles in a rectangular domain
• A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains

This page was built for publication: A divide-and-conquer algorithm for two-point \(L_1\) shortest path queries in polygonal domains

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