TY - GEN

T1 - Sparse geometric graphs with small dilation

AU - Aronov, Boris

AU - De Berg, Mark

AU - Cheong, Otfried

AU - Gudmundsson, Joachim

AU - Haverkort, Herman

AU - Vigneron, Antoine

N1 - Funding Information:
✩ B.A. was supported in part by NSF ITR Grant CCR-00-81964 and by a grant from the US–Israel Binational Science Foundation. Part of the work was carried out while B.A. was visiting TU/e in February 2004 and in the summer of 2005. O.C. was supported by LG Electronics. M.d.B. was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. M.S. was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). A.V. was supported by NUS research grant R-252-000-166-112. * Corresponding author. E-mail addresses: mdberg@win.tue.nl (M. de Berg), otfried@tclab.kaist.ac.kr (O. Cheong), joachim.gudmundsson@nicta.com.au (J. Gudmundsson), cs.herman@haverkort.net (H. Haverkort), michiel@scs.carleton.ca (M. Smid), antoine.vigneron@jouy.inra.fr (A. Vigneron). URL: http://cis.poly.edu/~aronov (B. Aronov). 1 NICTA is funded through the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33744953548&partnerID=8YFLogxK

U2 - 10.1007/11602613_7

DO - 10.1007/11602613_7

M3 - Conference contribution

AN - SCOPUS:33744953548

SN - 3540309357

SN - 9783540309352

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 50

EP - 59

BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings

T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005

Y2 - 19 December 2005 through 21 December 2005

ER -