Sparse geometric graphs with small dilation

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Given a set S of n points in the plane, 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, and dilation O(n/(k + 1)) can be computed in time O(n log n). We also construct 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)
    Title of host publicationAlgorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
    Pages50-59
    Number of pages10
    DOIs
    StatePublished - 2005
    Event16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China
    Duration: Dec 19 2005Dec 21 2005

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume3827 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other16th International Symposium on Algorithms and Computation, ISAAC 2005
    CountryChina
    CityHainan
    Period12/19/0512/21/05

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    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., & Vigneron, A. (2005). Sparse geometric graphs with small dilation. In Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings (pp. 50-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS). https://doi.org/10.1007/11602613_7