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 journalArticlepeer-review


    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
    Issue number3
    StatePublished - Aug 2008


    • 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


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

    Cite this