LIPIcs.SWAT.2016.25.pdf
- Filesize: 0.62 MB
- 14 pages
Document
A Plane 1.88-Spanner for Points in Convex Position
Authors
-
Part of:
Volume:
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-22
Cite As Get BibTex
Mahdi Amani, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, and Michiel Smid. A Plane 1.88-Spanner for Points in Convex Position. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SWAT.2016.25
Abstract
Let S be a set of n points in the plane that is in convex position. For a real number t>1, we say that a point p in S is t-good if for every point q of S, the shortest-path distance between p and q along the boundary of the convex hull of S is at most t times the Euclidean distance between p and q. We prove that any point that is part of (an approximation to) the diameter of S is 1.88-good. Using this, we show how to compute a plane 1.88-spanner of S in O(n) time, assuming that the points of S are given in sorted order along their convex hull. Previously, the best known stretch factor for plane spanners was 1.998 (which, in fact, holds for any point set, i.e., even if it is not in convex position).
Subject Classification
Keywords
- points in convex position
- plane spanner
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
R. V. Benson. Euclidean geometry and convexity. McGraw-Hill, 1966.
-
A. L. Cauchy. Note sur divers théorèmes relatifs á la rectification des courbes et á la quadrature des surfaces. C. R. Acad. Sci. Paris, 13:1060-1065, 1841.
-
T. M. Chan. A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM, 57(3), 2010.
-
L. P. Chew. There is a planar graph almost as good as the complete graph. In Proceedings of the 2nd ACM Symposium on Computational Geometry, pages 169-177, 1986.
-
L. P. Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39:205-219, 1989.
-
S. Cui, I. A. Kanj, and G. Xia. On the stretch factor of Delaunay triangulations of points in convex position. Computational Geometry: Theory and Applications, 44:104-109, 2011.
-
D. P. Dobkin, S. J. Friedman, and K. J. Supowit. Delaunay graphs are almost as good as complete graphs. Discrete &Computational Geometry, 5:399-407, 1990.
-
A. Dumitrescu and A. Ghosh. Lower bounds on the dilation of plane spanners. In Proceedings of the 2nd International Conference on Algorithms and Discrete Applied Mathematics, CALDAM, pages 139-151, 2016.
-
R. Janardan. On maintaining the width and diameter of a planar point-set online. Int. J. Comput. Geometry Appl., 3(3):331-344, 1993.
-
J. M. Keil and C. A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discrete &Computational Geometry, 7:13-28, 1992.
-
W. Mulzer. Minimum dilation triangulations for the regular n-gon. Master’s thesis, Freie Universität Berlin, Germany, 2004.
-
G. Narasimhan and M. Smid. Geometric Spanner Networks. Cambridge University Press, Cambridge, UK, 2007.
-
G. Xia. The stretch factor of the Delaunay triangulation is less than 1.998. SIAM Journal on Computing, 42:1620-1659, 2013.