-greedy t-spanner

DOI10.1007/978-3-319-62127-2_8MaRDI QIDQ2405280zbMATH OpenOpenAlexFDO

Authors Gali Bar-On, Paz Carmi

Publication date 22 September 2017

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

Mathematics Subject Classification ID

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

Abstract: We introduce a new geometric spanner, $delta$-Greedy, whose construction is based on a generalization of the known Path-Greedy and Gap-Greedy spanners. The $delta$-Greedy spanner combines the most desirable properties of geometric spanners both in theory and in practice. More specifically, it has the same theoretical and practical properties as the Path-Greedy spanner: a natural definition, small degree, linear number of edges, low weight, and strong $(1+varepsilon)$-spanner for every $varepsilon>0$. The $delta$-Greedy algorithm is an improvement over the Path-Greedy algorithm with respect to the number of shortest path queries and hence with respect to its construction time. We show how to construct such a spanner for a set of $n$ points in the plane in $O(n^{2}logn)$ time. The $delta$-Greedy spanner has an additional parameter, $delta$, which indicates how close it is to the Path-Greedy spanner on the account of the number of shortest path queries. For $delta=t$ the output spanner is identical to the Path-Greedy spanner, while the number of shortest path queries is, in practice, linear. Finally, we show that for a set of $n$ points placed independently at random in a unit square the expected construction time of the $delta$-Greedy algorithm is $O(nlogn)$. Our analysis indicates that the $delta$-Greedy spanner gives the best results among the known spanners of expected $O(nlogn)$ time for random point sets. Moreover, the analysis implies that by setting $delta=t$, the $delta$-Greedy algorithm provides a spanner identical to the Path-Greedy spanner in expected $O(nlogn)$ time.

Recommendations

• Distribution-sensitive construction of the greedy spanner
• Distribution-sensitive construction of the greedy spanner
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• A framework for computing the greedy spanner
• Computing the greedy spanner in linear space

Cited in

(2)

• On path-greedy geometric spanners
• Light Euclidean Spanners with Steiner Points

This page was built for publication: \(\delta\)-greedy \(t\)-spanner

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