2021
An improved construction for spanners of disks
Publication
Publication
Computational Geometry , Volume 92
Let D be a set of n pairwise disjoint disks in the plane. Consider the metric space in which the distance between any two disks D and D′ in D is the length of the shortest line segment that connects D and D′. For any real number ε>0, we show how to obtain a (1+ε)-spanner for this metric space that has at most (2π/ε)⋅n edges. The previously best known result is by Bose et al. (2011) [1]. Their (1+ε)-spanner is a variant of the Yao graph and has at most (8π/ε)⋅n edges. Our new spanner is also a variant of the Yao graph.
Additional Metadata | |
---|---|
Disk spanners, Geometric spanners, Yao graph | |
dx.doi.org/10.1016/j.comgeo.2020.101682 | |
Computational Geometry | |
Organisation | School of Computer Science |
Smid, M. (2021). An improved construction for spanners of disks. Computational Geometry, 92. doi:10.1016/j.comgeo.2020.101682
|