%0 Journal Article %1 abcehkw-osaar-05 %A Asano, Tetsuo %A de Berg, Mark %A Cheong, Otfried %A Everett, Hazel %A Haverkort, Herman %A Katoh, Naoki %A Wolff, Alexander %D 2005 %J Computational Geometry: Theory and Applications %K Manhattan_distance dilation_optimization geometric_spanners isothetic_rectangles myown %N 1 %P 59--77 %R 10.1016/j.comgeo.2004.09.001 %T Optimal Spanners for Axis-Aligned Rectangles %V 30 %X The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the $L_1$-distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their $L_1$-distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles. We study the following problem: given $n$ non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i) for arbitrary graphs, the problem is NP-hard; (ii) for trees, we can solve the problem by linear programming on $O(n^2)$ variables and constraints; (iii) for paths, we can solve the problem in time $O(n^3łog n)$; (iv) for rectangles sorted vertically along a path, the problem can be solved in $O(n^2)$ time, and a $(1+\varepsilon)$-approximation can be computed in linear time.

@article{abcehkw-osaar-05, abstract = {The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the $L_1$-distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their $L_1$-distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles. \par We study the following problem: given $n$ non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i) for arbitrary graphs, the problem is NP-hard; (ii) for trees, we can solve the problem by linear programming on $O(n^{2})$ variables and constraints; (iii) for paths, we can solve the problem in time $O(n^{3}\log n)$; (iv) for rectangles sorted vertically along a path, the problem can be solved in $O(n^{2})$ time, and a $(1+\varepsilon)$-approximation can be computed in linear time.}, added-at = {2024-02-18T09:53:56.000+0100}, author = {Asano, Tetsuo and de Berg, Mark and Cheong, Otfried and Everett, Hazel and Haverkort, Herman and Katoh, Naoki and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2a35bbb1de9d308dff1ee055a71f3f9bd/awolff}, doi = {10.1016/j.comgeo.2004.09.001}, interhash = {3031b798e6bafc377afb643e99ddca9e}, intrahash = {a35bbb1de9d308dff1ee055a71f3f9bd}, journal = {Computational Geometry: Theory and Applications}, keywords = {Manhattan_distance dilation_optimization geometric_spanners isothetic_rectangles myown}, number = 1, pages = {59--77}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/abcehkw-osaar-05.pdf}, succeeds = {abcehkw-osaar-04}, timestamp = {2024-02-18T12:36:59.000+0100}, title = {Optimal Spanners for Axis-Aligned Rectangles}, volume = 30, year = 2005 }