skip to main content
10.1145/1137856.1137897acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
Article

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

Published: 05 June 2006 Publication History

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 PR2, 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 PP. 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 P0 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.

Cited By

View all

Index Terms

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

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry
    June 2006
    500 pages
    ISBN:1595933409
    DOI:10.1145/1137856
    • Program Chairs:
    • Nina Amenta,
    • Otfried Cheong
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 05 June 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. complete graph
    2. dilation
    3. geometric network
    4. lower bound
    5. plane graph
    6. spanning ratio
    7. stretch factor
    8. triangulation

    Qualifiers

    • Article

    Conference

    SoCG06

    Acceptance Rates

    Overall Acceptance Rate 625 of 1,685 submissions, 37%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media