An \(O(n^{5/2}\log n)\) algorithm for the rectilinear minimum link-distance problem in three dimensions
From MaRDI portal
Publication:1025292
DOI10.1016/j.comgeo.2008.04.006zbMath1166.65318OpenAlexW2016840986MaRDI QIDQ1025292
Clifford Stein, David P. Wagner, Robert L. Scot Drysdale
Publication date: 18 June 2009
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2008.04.006
algorithmsshortest pathpriority queueminimum link pathbinary space partitionsegment treesweep planerectilinear path
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
- Optimal parallel algorithms for rectilinear link-distance problems
- Rectilinear paths among rectilinear obstacles
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Optimal binary space partitions for orthogonal objects
- SHORTEST PATH QUERIES IN RECTILINEAR WORLDS
- On bends and distances of paths among obstacles in two-layer interconnection model
