Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 207-219 |
| Number of pages | 13 |
| Journal | Computational Geometry: Theory and Applications |
| Volume | 40 |
| Issue number | 3 |
| DOIs | |
| State | Published - Aug 2008 |
| Externally published | Yes |
Bibliographical note
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.
Keywords
- 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