Geodesic spanners for points in R^3 amid axis-parallel boxes

DOI10.1016/J.IPL.2020.106063MaRDI QIDQ2224857zbMATH OpenOpenAlexFDO

Authors Mohammad A. Abam, Mohammad Javad Rezaei Seraji

Publication date 4 February 2021

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

\(t\)-spannercomputational geometrygeodesic distancegeometric network

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Let $P$ be a set of $n$ points in $mathbb{R}^3$ amid a bounded number of obstacles. When obstacles are axis-parallel boxes, we prove that $P$ admits an $8sqrt3$-spanner with $O(nlo{g}^{3}n)$ edges with respect to the geodesic distance.

Recommendations

• Geodesic spanners for points on a polyhedral terrain
• Geodesic spanners for points on a polyhedral terrain
• Geometric Spanners for Points Inside a Polygonal Domain
• Spanners for geodesic graphs and visibility graphs
• Geodesic spanners on polyhedral surfaces

Cites work

• 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Bypassing the embedding
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Geodesic spanners for points on a polyhedral terrain
• Geometric Spanner Networks
• Geometric spanners for weighted point sets
• Kinetic spanners in \(\mathbb R^{d}\)
• On hierarchical routing in doubling metrics
• On sparse spanners of weighted graphs
• Searching dynamic point sets in spaces with bounded doubling dimension
• Spanners for geodesic graphs and visibility graphs
• The Moore bound for irregular graphs
• Walking around fat obstacles.

Cited in

(2)

• Geodesic spanners for points on a polyhedral terrain
• Realizing metric spaces with convex obstacles

This page was built for publication: Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes

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