Sparse geometric graphs with small dilation

Boris Aronov, Mark De Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, Antoine Vigneron

    Research output: Contribution to journalArticle

    Abstract

    Given a set S of n points in RD, and an integer k such that 0≤k<n, we show that a geometric graph with vertex set S, at most n-1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n-1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.

    Original languageEnglish (US)
    Pages (from-to)207-219
    Number of pages13
    JournalComputational Geometry: Theory and Applications
    Volume40
    Issue number3
    DOIs
    StatePublished - Aug 2008

    Keywords

    • Dilation
    • Geometric network
    • Small-dilation spanning tree
    • Spanner

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Sparse geometric graphs with small dilation'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., De Berg, M., Cheong, O., Gudmundsson, J., Haverkort, H., Smid, M., & Vigneron, A. (2008). Sparse geometric graphs with small dilation. Computational Geometry: Theory and Applications, 40(3), 207-219. https://doi.org/10.1016/j.comgeo.2007.07.004