Geodesic Spanners for Points on a Polyhedral Terrain

DOI10.1137/18M119358XzbMATH Open1430.52020arXiv1511.01612OpenAlexW2998615518WikidataQ126577624 ScholiaQ126577624MaRDI QIDQ5206937FDOQ5206937

Mohammad Javad Rezaei Seraji, Mark de Berg, Mohammad A. Abam

Publication date: 19 December 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: We show that there exists a geodesic spanner with almost linear number of edges.

Full work available at URL: https://arxiv.org/abs/1511.01612

zbMATH Keywords

approximation algorithmsgeometric spannerspolyhedral terrain

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Algorithms for approximation of functions (65D15)

Cites Work

• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• On hierarchical routing in doubling metrics
• Geometric Spanner Networks
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• On sparse spanners of weighted graphs
• The Moore bound for irregular graphs
• Geodesic Spanners on Polyhedral Surfaces
• Geometric spanners for weighted point sets
• Bypassing the embedding
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Kinetic spanners in \(\mathbb R^{d}\)
• Searching dynamic point sets in spaces with bounded doubling dimension
• Fully dynamic geometric spanners
• Geometric Spanners for Points Inside a Polygonal Domain

Cited In (3)

• Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Geometric Spanners for Points Inside a Polygonal Domain

This page was built for publication: Geodesic Spanners for Points on a Polyhedral Terrain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5206937)