Back to Search
Start Over
GEODESIC SPANNERS FOR POINTS ON A POLYHEDRAL TERRAIN.
- Source :
-
SIAM Journal on Computing . 2019, Vol. 48 Issue 6, p1796-1810. 15p. - Publication Year :
- 2019
-
Abstract
- Let S be a set of n points on a polyhedral terrain T in R³, and let ε > 0 be a fixed constant. We prove that S admits a (2 + ε)-spanner with O(n log n) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in \BbbR d admits an additively weighted (2 + ε)-spanner with O(n) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ε) and almost matches the lower bound. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 48
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 144787692
- Full Text :
- https://doi.org/10.1137/18m119358x