Planar spanners and approximate shortest path queries among obstacles in the plane

DOI10.1007/3-540-61680-2_79zbMath1379.68314OpenAlexW1481010420MaRDI QIDQ4595512

L. Paul Chew, Danny Z. Chen, Srinivasa R. Arikati, Christos D. Zaroliagis, Michiel H. M. Smid, Gautam K. Das

Publication date: 5 December 2017

Published in: Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61680-2_79

Mathematics Subject Classification ID

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

Related Items

On approximating tree spanners that are breadth first search trees, Linear-size planar Manhattan network for convex point sets, Euclidean Steiner Spanners: Light and Sparse, Planar rectilinear shortest path computation using corridors, Routing among convex polygonal obstacles in the plane, On plane geometric spanners: a survey and open problems, Algorithms for approximate shortest path queries on weighted polyhedral surfaces, Approximate distance oracles for graphs with dense clusters, On path-greedy geometric spanners, Tree spanners of bounded degree graphs, Querying two boundary points for shortest paths in a polygonal domain, Vertex Fault-Tolerant Geometric Spanners for Weighted Points, Near-linear-time deterministic plane Steiner spanners for well-spaced point sets, Emanation graph: a plane geometric spanner with Steiner points, Unnamed Item, I/O-efficient algorithms for computing planar geometric spanners, Tree spanners in planar graphs, Lower bounds for computing geometric spanners and approximate shortest paths, Shortest-path queries in static networks, A near linear time approximation scheme for Steiner tree among obstacles in the plane, Unnamed Item, Unnamed Item, Vertex fault-tolerant spanners for weighted points in polygonal domains, Unnamed Item, Many distances in planar graphs, Reachability oracles for directed transmission graphs, Computing an \(L_1\) shortest path among splinegonal obstacles in the plane, Unnamed Item