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

bridge graphDilation optimizationGeometric spannersIsothetic rectanglesManhattan distanceminimized dilatationoptimal spannerspolynomial complexityrectangles

Mathematics Subject Classification ID

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

Review text

The authors propose an approach to the problem of finding the connection segments that minimize the dilatation in a bridge graph, i.e. the graph which describes which pairs of rectangles from the given non-intersection rectangles are to be connected. It is proved that the graph contains cycles, then the problem cannot be solved in polynomial time, but if the graph is a path or a tree, then the problem has polynomial complexity. It is also proved that in the case of a set of rectangles sorted vertically along a path, an estimate of the problem solution can be found in linear time.

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

• 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
• 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?)
• There are planar graphs almost as good as the complete graph

Cited in

(4)

• Geometric Spanner of Objects under L 1 Distance
• A geometric spanner of segments
• 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)