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: [email protected] (M. de Berg), [email protected] (O. Cheong), [email protected] (J. Gudmundsson), [email protected] (H. Haverkort), [email protected] (M. Smid), [email protected] (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
UR - http://www.scopus.com/inward/citedby.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 -