Geodesic spanners for points on a polyhedral terrain

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

Research output: Contribution to journalArticleAcademic

75 Downloads (Pure)

Abstract

Let S be a set S of n points on a polyhedral terrain T in R3, and let " > 0 be a xed constant. We prove that S admits a (2 + ")-spanner with O(n log n) edges with respect to the geodesic distance. This is the rst 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 Rd 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
Number of pages13
JournalarXiv
Volume2016
Issue number1511.01612
Publication statusPublished - Nov 2015

Keywords

  • Computer Science > Computational Geometry

Fingerprint

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

Cite this