Near-linear-time deterministic plane Steiner spanners for well-spaced point sets. (English) Zbl 1329.05077
Summary: We describe an algorithm that takes as input \(n\) points in the plane and a parameter \(\epsilon\), and produces as output an embedded planar graph having the given points as a subset of its vertices in which the graph distances are a \((1+\epsilon)\)-approximation to the geometric distances between the given points. For point sets in which the Delaunay triangulation has sharpest angle \(\alpha\), our algorithm’s output has \(O(\frac{\beta^2}{\epsilon} n)\) vertices, its weight is \(O(\frac{\beta}{\alpha})\) times the minimum spanning tree weight where \(\beta = \frac{1}{\alpha \epsilon} \log \frac{1}{\alpha \epsilon}\). The algorithm’s running time, if a Delaunay triangulation is given, is linear in the size of the output. We use this result in a similarly fast deterministic approximation scheme for the traveling salesperson problem.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Althöfer, I.; Das, G.; Dobkin, D.; Joseph, D.; Soares, J., On sparse spanners of weighted graphs, Discrete Comput. Geom., 9, 1, 81-100 (1993), (93h:05161) · Zbl 0762.05039 |
| [2] | Arikati, S.; Chen, D. Z.; Chew, L.; Das, G.; Smid, M.; Zaroliagis, C., Planar spanners and approximate shortest path queries among obstacles in the plane, (Proc. 4th Eur. Symp. Alg.. Proc. 4th Eur. Symp. Alg., LNCS, vol. 1136 (1996)), 514-528 · Zbl 1379.68314 |
| [3] | Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, J. ACM, 45, 5, 753-782 (September 1998) · Zbl 1064.90566 |
| [4] | Arya, S.; Das, G.; Mount, D. M.; Salowe, J. S.; Smid, M., Euclidean spanners: short, thin, and lanky, (Proc. 27th ACM Symp. Theory of Computing (1995)), 489-498 · Zbl 0968.68533 |
| [5] | Bern, M.; Eppstein, D.; Gilbert, J., Provably good mesh generation, J. Comput. Syst. Sci., 48, 3, 384-409 (1994) · Zbl 0799.65119 |
| [6] | Bern, M.; Eppstein, D.; Teng, S.-H., Parallel construction of quadtrees and quality triangulations, Int. J. Comput. Geom. Appl., 9, 6, 517-532 (1999) · Zbl 1074.68630 |
| [7] | Borradaile, G.; Demaine, E.; Tazari, S., Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Algorithmica, 68, 2, 287-311 (February 2014) · Zbl 1303.05183 |
| [8] | Borradaile, G.; Klein, P.; Mathieu, C., An \(O(n \log n)\) approximation scheme for Steiner tree in planar graphs, ACM Trans. Algorithms, 5, 3, 1-31 (2009) · Zbl 1300.05294 |
| [9] | Bose, P.; Devroye, L.; Löffler, M.; Snoeyink, J.; Verma, V., The spanning ratio of the Delaunay triangulation is greater than \(\pi / 2\), (Proc. 21st Canad. Conf. Comput. Geom. (2009)) |
| [10] | Buchin, K.; Mulzer, W., Delaunay triangulations in \(O(sort(n))\) time and more, J. ACM, 58, 2, A6 (2011) · Zbl 1327.68311 |
| [11] | Chazelle, B.; Edelsbrunner, H., An optimal algorithm for intersecting line segments in the plane, J. ACM, 39, 1, 1-54 (1992) · Zbl 0799.68191 |
| [12] | Eppstein, D., Spanning trees and spanners, (Handbook of Computational Geometry (2000), Elsevier), 425-461, Chapter 9 · Zbl 0944.05021 |
| [13] | Han, Y.; Thorup, M., Integer sorting in \(O(n \sqrt{\log \log n})\) expected time and linear space, (Proc. 43rd Annual Symp. Foundations of Computer Science (2002)), 135-144 |
| [14] | Klein, P., A subset spanner for planar graphs, with application to subset TSP, (Proc. 38th ACM Symp. Theory of Computing (2006)), 749-756 · Zbl 1301.05335 |
| [15] | Klein, P., A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights, SIAM J. Comput., 37, 6, 1926-1952 (2008) · Zbl 1155.68090 |
| [16] | Mitchell, J. S.B., Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, \(k\)-MST, and related problems, SIAM J. Comput., 28, 4, 1298-1309 (1999) · Zbl 0940.68062 |
| [17] | Narasimhan, G.; Smid, M., Geometric Spanner Networks (2007), Cambridge University Press · Zbl 1140.68068 |
| [18] | Radin, C.; Sadun, L., The isoperimetric problem for pinwheel tilings, Commun. Math. Phys., 177, 1, 255-263 (1996) · Zbl 0864.52012 |
| [19] | Rao, S. B.; Smith, W. D., Approximating geometrical graphs via “spanners” and “banyans”, (Proc. 30th ACM Symp. Theory of Computing (1998)), 540-550 · Zbl 1027.68651 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
