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: Annette Ebbers-Baumann , Rolf Klein , Elmar Langetepe , Andrzej Lingas, A fast algorithm for approximating the detour of a polygonal chain, Computational Geometry: Theory and Applications, v.27 n.2, p.123-134, February 2004 [doi>10.1016/S0925-7721(03)00046-4]
• 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: Annette Ebbers-Baumann , Ansgar Grune , Rolf Klein, The Geometric Dilation of Finite Point Sets, Algorithmica, v.44 n.2, p.137-149, February 2006 [doi>10.1007/s00453-005-1203-9]
• 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: David Eppstein , Kevin A. Wortman, Minimum dilation stars, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064142]
• 12: Dan Ismailescu , Radoš Radoičić, A dense planar point set from iterated line intersections, Computational Geometry: Theory and Applications, v.27 n.3, p.257-267, March 2004 [doi>10.1016/j.comgeo.2003.10.002]
• 13: S. Kamali. On the Density of Iterated Segment Intersections. Diploma Thesis. Bonn, 2005.
• 14: J. Mark Keil , Carl A. Gutwin, Classes of graphs which approximate the complete Euclidean graph, Discrete & Computational Geometry, v.7 n.1, p.13-28, 1992 [doi>10.1007/BF02187821]
• 15: D. Lorenz. On the Dilation of Finite Point Sets. Diploma Thesis. Bonn, 2005.
• 16: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 17: Giri Narasimhan , Michiel Smid, Approximating the Stretch Factor of Euclidean Graphs, SIAM Journal on Computing, v.30 n.3, p.978-989, 2000 [doi>10.1137/S0097539799361671]
• 18: G. Narasimhan and M. Smid. Geometric Spanner Networks. Cambridge University Press, to appear.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Theory

Keywords:
complete graph, dilation, geometric network, lower bound, plane graph, spanning ratio, stretch factor, triangulation