Optimal spanners for axis-aligned rectangles

DOI10.1016/j.comgeo.2004.09.001zbMath1066.65025OpenAlexW2131984062MaRDI QIDQ706725

Tetsuo Asano, Alexander Wolff, Hazel Everett, Naoki Katoh, Herman J. Haverkort, Otfried Schwarzkopf, Mark T. de Berg

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)

Related Items

A GEOMETRIC SPANNER OF SEGMENTS ⋮ Geometric Spanner of Objects under L 1 Distance ⋮ Geometric Spanner of Segments ⋮ The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing

Cites Work

• A new polynomial-time algorithm for linear programming
• There are planar graphs almost as good as the complete graph
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Graph spanners
• A general approach to dominance in the plane
• Unnamed Item
• Unnamed Item
• Unnamed Item