Geodesic spanners for points on a polyhedral terrain

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

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

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

Recommendations

• Geodesic spanners for points on a polyhedral terrain
• Geodesic spanners on polyhedral surfaces
• Geometric Spanners for Weighted Point Sets
• Geometric spanners for weighted point sets
• Spanners of Additively Weighted Point Sets

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 (10)

• Geodesic spanners on polyhedral surfaces
• Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Spanners of Additively Weighted Point Sets
• Geodesic spanners for points on a polyhedral terrain
• The complexity of geodesic spanners
• The complexity of geodesic spanners
• Spanners of additively weighted point sets
• Geometric Spanners for Points Inside a Polygonal Domain
• Spanners for geodesic graphs and visibility graphs

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)