Geodesic Spanners for Points on a Polyhedral Terrain
Abam, MA Mohammad Ali, Berg, MT Mark de, Mohammad Javad Rezaei Seraji · TU/e Research Portal · 2015
Let S be a set of n points on a polyhedral terrain \\scrT in \\BbbR 3 , and let \\varepsilon > 0 be a fixed constant. We prove that S admits a (2 + \\varepsilon )-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 + \\varepsilon )-spanner with O(n) edges; this improves the previously best known bound on the spanning ratio (which was 5 + \\varepsilon ) and almost matches the lower bound.