Geodesic spanners for points on a polyhedral terrain

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

doi:10.1137/1.9781611974782.161

Geodesic spanners for points on a polyhedral terrain

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 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 language	English
Title of host publication	Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Editors	Philip N. Klein
Publisher	Society for Industrial and Applied Mathematics (SIAM)
Pages	2434-2442
Number of pages	9
ISBN (Electronic)	978-1-61197-478-2
DOIs	https://doi.org/10.1137/1.9781611974782.161
Publication status	Published - 2017
Event	28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 Conference number: 28

Conference

Conference	28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
Abbreviated title	SODA 2017
Country/Territory	Spain
City	Barcelona
Period	16/01/17 → 19/01/17

Access to Document

10.1137/1.9781611974782.161

Cite this

@inproceedings{5ff946b8b88a4c97a0295591f0b861b5,

title = "Geodesic spanners for points on a polyhedral terrain",

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.",

author = "M.A. Abam and \{de Berg\}, M.T. and \{Javad Rezaei Seraji\}, Mohammad",

year = "2017",

doi = "10.1137/1.9781611974782.161",

language = "English",

pages = "2434--2442",

editor = "Klein, \{Philip N.\}",

booktitle = "Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

address = "United States",

note = "28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), SODA 2017 ; Conference date: 16-01-2017 Through 19-01-2017",

}

Abam, MA, de Berg, MT & Javad Rezaei Seraji, M 2017, Geodesic spanners for points on a polyhedral terrain. in PN Klein (ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics (SIAM), pp. 2434-2442, 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 16/01/17. https://doi.org/10.1137/1.9781611974782.161

Geodesic spanners for points on a polyhedral terrain. / Abam, M.A.; de Berg, M.T.; Javad Rezaei Seraji, Mohammad .
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Philip N. Klein. Society for Industrial and Applied Mathematics (SIAM), 2017. p. 2434-2442.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Geodesic spanners for points on a polyhedral terrain

AU - Abam, M.A.

AU - de Berg, M.T.

AU - Javad Rezaei Seraji, Mohammad

N1 - Conference code: 28

PY - 2017

Y1 - 2017

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

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

UR - https://www.scopus.com/pages/publications/85016191433

U2 - 10.1137/1.9781611974782.161

DO - 10.1137/1.9781611974782.161

M3 - Conference contribution

SP - 2434

EP - 2442

BT - Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Klein, Philip N.

PB - Society for Industrial and Applied Mathematics (SIAM)

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

Y2 - 16 January 2017 through 19 January 2017

ER -

Geodesic spanners for points on a polyhedral terrain

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this