The density of iterated crossing points and a gap result for triangulations of finite point sets

ABSTRACT

Consider a plane graph G, drawn with straight lines. For every pair a,b of vertices of G, we compare the shortest-path distance between a and b in G (with Euclidean edge lengths) to their actual distance in the plane. The worst-case ratio of these two values, for all pairs of points, is called the dilation of G. All finite plane graphs of dilation 1 have been classified. They are closely related to the following iterative procedure. For a given point set P ⊆ R², we connect every pair of points in P by a line segment and then add to P all those points where two such line segments cross. Repeating this process infinitely often, yields a limit point set P^∞⊇P. This limit set P^∞ is finite if and only if P is contained in the vertex set of a triangulation of dilation 1.The main result of this paper is the following gap theorem: For any finite point set P in the plane for which P^∞ is infinite, there exists a threshold λ > 1 such that P is not contained in the vertex set of any finite plane graph of dilation at most λ. As a first ingredient to our proof, we show that such an infinite P^∞ must lie dense in a certain region of the plane. In the second, more difficult part, we then construct a concrete point set P₀ such that any planar graph that contains this set amongst its vertices must have a dilation larger than 1.0000047.

References

1. P. Agarwal, R. Klein, Ch. Knauer, S. Langerman, P. Morin, M. Sharir, and M. Soss. Computing the Detour and Spanning Ratio of Paths, Trees and Cycles in 2D and 3D. To appear in Discrete Comput. Geom., 2006.
2. K. Bezdek and J. Pach. A Point Set Everywhere Dense in the Plane. Elemente der Mathematik 40(4): 81--84, 1985.
3. A. Dumitrescu, A. Ebbers-Baumann, A. Grüne, R. Klein, and G. Rote, On the Geometric Dilation of Closed Curves, Graphs, and Point Sets. To appear in Computational Geometry: Theory and Applications, 2006.
4. A. Dumitrescu, A. Ebbers-Baumann, A. Grüne, R. Klein, and G. Rote. On Geometric Dilation and Halving Chords. In F. Dehne, A. López-Ortiz, J.-R. Sack (eds.) Proceedings WADS'05, pp. 244--255, LNCS 3608, Springer-Verlag, 2005.
5. A. Ebbers-Baumann, R. Klein, E. Langetepe, and A. Lingas. A Fast Algorithm for Approximating the Detour of a Polygonal Chain. Computational Geometry: Theory and Applications, 27:123--134, 2004.
6. A. Ebbers-Baumann, A. Grüne, and R. Klein. Geometric Dilation of Closed Planar Curves: New Lower Bounds. To appear in Computational Geometry: Theory and Applications, 2006.
7. A. Ebbers-Baumann, A. Grüne, and R. Klein. On the Geometric Dilation of Finite Point Sets. Algorithmica 44(2), pp. 137--149, 2006.
8. A. Ebbers-Baumann, A. Grüne, M. Karpinski, R. Klein, Ch. Knauer, and A. Lingas. Embedding Point Sets into Plane Graphs of Small Dilation. In X. Deng und D. Du (eds.) Proceedings ISAAC 2005, pp. 5--16, LNCS 3827, Springer-Verlag, 2005.
9. D. Eppstein. Spanning trees and spanners. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia (eds.), pp. 425-461. Elsevier, 1999.
10. D. Eppstein. The Geometry Junkyard. http://www.ics.uci.edu/~eppstein/junkyard/dilation-free/.
11. D. Eppstein and A. Wortman. Minimum Dilation Stars. Proceedings 21th Annual ACM Symposium on Computational Geomtry, pp. 321--326, 2005.
12. D. Ismailescu and R. Radoičić. A Dense Planar Point Set from Iterated Line Intersections. Computational Geometry: Theory and Applications, 27(3), pp. 257--267, 2004.
13. S. Kamali. On the Density of Iterated Segment Intersections. Diploma Thesis. Bonn, 2005.
14. J.M. Keil and C.A. Gutwin. The Delaunay Triangulation Closely Approximates the Complete Euclidean Graph. Discrete Comput. Geom. 7, 1992, pp. 13--28.
15. D. Lorenz. On the Dilation of Finite Point Sets. Diploma Thesis. Bonn, 2005.
16. J. Matouvsek. Lectures on Discrete Geometry. Graduate Texts in Mathematics. Springer-Verlag, 2000.
17. G. Narasimhan and M. Smid. Approximating the Stretch Factor of Euclidean Graphs. SIAM J. Comput. 30(3), 2000, pp. 978--989.
18. G. Narasimhan and M. Smid. Geometric Spanner Networks. Cambridge University Press, to appear.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory