Geodesic spanners for points on a polyhedral terrain

M.A. Abam, M.T. de Berg, Mohammad Javad Rezaei Seraji

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

Let S be a set S of n points on a polyhedral terrain T in ℝ3, 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 ℝ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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
EditorsPhilip N. Klein
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages2434-2442
Number of pages9
ISBN (Electronic)978-1-61197-478-2
DOIs
Publication statusPublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain
Duration: 16 Jan 201719 Jan 2017
Conference number: 28

Conference

Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
Abbreviated titleSODA 2017
CountrySpain
CityBarcelona
Period16/01/1719/01/17

Fingerprint Dive into the research topics of 'Geodesic spanners for points on a polyhedral terrain'. Together they form a unique fingerprint.

Cite this