Abstract
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound >1. In this paper we provide the first upper and lower bounds for the embedding problem.
-
1
Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247.
-
2
Each embedding of a closed convex curve has dilation ≥ 1.00157.
-
3
Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation \(\geq 2/\sqrt{3} \approx 1.1547\).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P., Klein, R., Knauer, C., Langerman, S., Morin, P., Sharir, M., Soss, M.: Computing the Detour and Spanning Ratio of Paths, Trees and Cycles in 2D and 3D (2005) (manuscript, submitted for publication)
Apostol, T.M.: Dirichlet Series in Number Theory, 2nd edn., pp. 148–155. Springer, Heidelberg (1997)
Arikati, S.R., Chen, D.Z., Chew, L.P., Das, G., Smid, M.: Planar Spanners and Approximate Shortest Path Queries Among Obstacles in the Plane. In: DĂaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 514–528. Springer, Heidelberg (1996)
Das, G., Joseph, D.: Which Triangulations Approximate the Complete Graph? In: Djidjev, H.N. (ed.) Optimal Algorithms. LNCS, vol. 401, pp. 168–192. Springer, Heidelberg (1989)
Dobkin, D.P., Friedman, S.J., Supowit, K.J.: Delaunay Graphs Are Almost as Good as Complete Graphs. Discrete & Computational Geometry 5, 399–407 (1990)
Dumitrescu, A., GrĂ¼ne, A., Rote, G.: On the Geometric Dilation of Curves and Point Sets (2004) (manuscript)
Dumitrescu, A., Ebbers-Baumann, A., GrĂ¼ne, A., Klein, R., Rote, G.: On Geometric Dilation and Halving Chords. In: Dehne, F., LĂ³pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 244–255. Springer, Heidelberg (2005)
Ebbers-Baumann, A., GrĂ¼ne, A., Klein, R.: On the Geometric Dilation of Finite Point Sets. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 250–259. Springer, Heidelberg (2003)
Ebbers-Baumann, A., GrĂ¼ne, A., Klein, R.: Geometric Dilation of Closed Planar Curves: New Lower Bounds. To appear in Computational Geometry: Theory and Applications
Ebbers-Baumann, A., Klein, R., Langetepe, E., Lingas, A.: A Fast Algorithm for Approximating the Detour of a Polygonal Chain. Computational Geometry: Theory and Applications 27, 123–134 (2004)
Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425–461. Elsevier, Amsterdam (1999)
Eppstein, D.: The Geometry Junkyard, http://www.ics.uci.edu/~eppstein/junkyard/dilation-free/
Eppstein, D., Hart, D.: Shortest Paths in an Arrangement with k Line Orientations. In: Proceedings 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 310–316 (1999)
Fekete, S., Klein, R., NĂ¼chter, A.: Online Searching with an Autonomous Robot. In: Workshop on Algorithmic Foundations of Robotics (2004)
Hlawka, E.: Theorie der Gleichverteilung. BI Wissenschaftsverlag
Keil, J.M., Gutwin, C.A.: The Delaunay Triangulation Closely Approximates the Complete Euclidean Graph. Discrete Comput. Geom. 7, 13–28 (1992)
Lorenz, D.: On the Dilation of Finite Point Sets. Diploma Thesis. Bonn (2005)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (to appear)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ebbers-Baumann, A., GrĂ¼ne, A., Karpinski, M., Klein, R., Knauer, C., Lingas, A. (2005). Embedding Point Sets into Plane Graphs of Small Dilation. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_3
Download citation
DOI: https://doi.org/10.1007/11602613_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)