Geodesic spanners for points on a polyhedral terrain

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

Research output: Contribution to journalArticleAcademic

97 Downloads (Pure)


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
Issue number1511.01612
Publication statusPublished - Nov 2015


  • Computer Science > Computational Geometry


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

Cite this