AbstractGiven a set S of n points in the plane, we define a Manhattan Network on S as a rectilinear network G with the property that for every pair of points in S, the network G contains the shortest rectilinear path between them. A Minimum Manhattan Network on S is a Manhattan network of minimum possible length. A Manhattan network can be thought of as a graph G=(V,E), where the vertex set V corresponds to points from S and a set of Steiner points S', and the edges in E correspond to horizontal or vertical line segments connecting points in S U S'. A Manhattan network can also be thought of as a 1-spanner (for the L1-metric) for the points in S.
Let R be an algorithm that produces a rectangulation of a staircase polygon in time R(n) of weight at most r times the optimal. We design an O(n\log n + R(n)) time algorithm which, given a set S of n points in the plane, produces a Manhattan network on S with total weight at most 4r times that of a minimum Manhattan network. Using known rectangulation algorithms, this gives us an O(n3)-time algorithm with approximation factor four, and an O(n \log n)-time algorithm with approximation factor eight.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Additional Key Words and Phrases: computational geometry, approximation algorithms, spanners
Selected references
- Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, and Michiel Smid. Euclidean spanners: Short, thin, and lanky. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 489-498, Las Vegas, Nevada, 29 May-1 June 1995.
- Christos Levcopoulos and Drago Krznaric. A fast heuristic for approximating the minimum weight triangulation (extended abstract). In Rolf G. Karlsson and Andrzej Lingas, editors, SWAT '96, 5th Scandinavian Workshop on Algorithm Theory, volume 1097 of Lecture Notes in Computer Science, pages 296-308, Reykjavík, Iceland, 3-5 July 1996. Springer.
- Christos Levcopoulos and Drago Krznaric. A fast heuristic for approximating the minimum weight triangulation (extended abstract). In Rolf G. Karlsson and Andrzej Lingas, editors, SWAT '96, 5th Scandinavian Workshop on Algorithm Theory, volume 1097 of Lecture Notes in Computer Science, pages 296-308, Reykjavík, Iceland, 3-5 July 1996. Springer.