@inproceedings{a4eea979bea749089ee0303d626111c8,

title = "Sparse geometric graphs with small dilation",

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.",

author = "Boris Aronov and {De Berg}, Mark and Otfried Cheong and Joachim Gudmundsson and Herman Haverkort and Antoine Vigneron",

year = "2005",

month = dec,

day = "1",

doi = "10.1007/11602613_7",

language = "English (US)",

isbn = "3540309357",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "50--59",

booktitle = "Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings",

note = "16th International Symposium on Algorithms and Computation, ISAAC 2005 ; Conference date: 19-12-2005 Through 21-12-2005",

}