Back to Search
Start Over
Local Geometric Spanners.
- Source :
-
Algorithmica . Dec2021, Vol. 83 Issue 12, p3629-3648. 20p. - Publication Year :
- 2021
-
Abstract
- We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set P and a region R belonging to a family R , we define G ∩ R to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t R is a geometric graph G on P such that for any region R ∈ R , the graph G ∩ R is a t-spanner for K (P) ∩ R , where K (P) is the complete geometric graph on P. For any set P of n points and any constant ε > 0 , we prove that P admits local (1 + ε) -spanners of sizes O (n log 6 n) and O (n log n) w.r.t axis-parallel squares and vertical slabs, respectively. If adding Steiner points is allowed, then local (1 + ε) -spanners with O(n) edges and O (n log 2 n) edges can be obtained for axis-parallel squares and disks using O(n) Steiner points, respectively. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 83
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 153626162
- Full Text :
- https://doi.org/10.1007/s00453-021-00860-5