AbstractGiven a set

Sofnpoints in the plane, we define aManhattan NetworkonSas a rectilinear networkGwith the property that for every pair of points inS, the networkGcontains the shortest rectilinear path between them. AMinimum Manhattan NetworkonSis a Manhattan network of minimum possible length. A Manhattan network can be thought of as a graphG=(V,E), where the vertex setVcorresponds to points fromSand a set of Steiner pointsS', and the edges inEcorrespond to horizontal or vertical line segments connecting points inSUS'. A Manhattan network can also be thought of as a 1-spanner (for theL_{1}-metric) for the points inS.Let

Rbe an algorithm that produces a rectangulation of a staircase polygon in timeR(n)of weight at mostrtimes the optimal. We design an O(n\logn+R(n)) time algorithm which, given a setSofnpoints in the plane, produces a Manhattan network onSwith total weight at most 4rtimes that of a minimum Manhattan network. Using known rectangulation algorithms, this gives us an O(n^{3})-time algorithm with approximation factor four, and an O(n\logn)-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.