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