Optimal spanners for axis-aligned rectangles

DOI10.1016/J.COMGEO.2004.09.001MaRDI QIDQ706725zbMATH OpenOpenAlexFDO

Authors Tetsuo Asano, Hazel Everett, Naoki Katoh, Alexander Wolff, Mark de Berg, Otfried Cheong, Herman Haverkort

Publication date 9 February 2005

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2004.09.001

zbMATH Keywords

polynomial complexityrectanglesManhattan distancebridge graphDilation optimizationGeometric spannersIsothetic rectanglesminimized dilatationoptimal spanners

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Geometric Spanner of Objects under L 1 Distance
• Computing minimum dilation spanning trees in geometric graphs
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• Computing geometric minimum-dilation graphs is NP-hard
• Computing a minimum-dilation spanning tree is NP-hard

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• A general approach to dominance in the plane
• A new polynomial-time algorithm for linear programming
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Graph spanners
• There are planar graphs almost as good as the complete graph

Cited in

(4)

• Geometric Spanner of Segments
• Geometric Spanner of Objects under L 1 Distance
• A geometric spanner of segments
• The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing

This page was built for publication: Optimal spanners for axis-aligned rectangles

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