The Complexity of Geodesic Spanners

Abstract

A geometric \(t\)-spanner for a set \(S\) of \(n\) point sites is an edge-weighted graph for which the (weighted) distance between any two sites \(p,q \in S\) is at most \(t\) times the original distance between \(p\) and \(q\). We study geometric \(t\)-spanners for point sets in a constrained two-dimensional environment \(P\). In such cases, the edges of the spanner may have non-constant complexity. Hence, we introduce a novel spanner property: the spanner complexity, that is, the total complexity of all edges in the spanner. Let \(S\) be a set of \(n\) point sites in a simple polygon \(P\) with \(m\) vertices. We present an algorithm to construct, for any fixed integer \(k \geq 1\), a \(2\sqrt{2}k\)-spanner with complexity \(O(mn^{1/k} + n\log^2 n)\) in \(O(n\log^2n + m\log n + K)\) time, where \(K\) denotes the output complexity. When we relax the restriction that the edges in the spanner are shortest paths, such that an edge in the spanner can be any path between two sites, we obtain for any constant \(\varepsilon \in (0,2k)\) a relaxed geodesic \((2k + \eps)\)-spanner of the same complexity, where the constant is dependent on \(\varepsilon\). When we consider sites in a polygonal domain \(P\) with holes, we can construct a relaxed geodesic \(6k\)-spanner of complexity \(O(mn^{1/k} + n\log^2 n)\) in \(O((n+m)\log^2n\log m+ K)\) time. Additionally, for any constant \(\varepsilon \in (0,1)\) and integer constant \(t \geq 2\), we show a lower bound for the complexity of any \((t-\varepsilon)\)-spanner of \(\Omega(mn^{1/(t-1)} + n)\).

Corresponding Publications

The Complexity of Geodesic Spanners

Sarita de Berg, Marc van Kreveld, Frank Staals

Proc. 39th Annual Symposium on Computational Geometry, 2023

@inproceedings{geodesic_spanners2023,
  author = {de Berg, Sarita and van Kreveld, Marc and Staals, Frank},
  title = {The Complexity of Geodesic Spanners},
  booktitle = {Proc. 39th Annual Symposium on Computational Geometry},
  year = {2023},
  location = {Dallas, United States},
  keywords = {spanner, simple polygon, geodesic distance, complexity},
  category = {geodesic},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.SoCG.2023.16},
  pages = {16:1--16:16},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2023.16},
  volume = {258},
}

The complexity of geodesic spanners

Sarita de Berg, Marc van Kreveld, Frank Staals

Abstr. 38th European Workshop on Computational Geometry (EuroCG), 2022

@article{spanners_eurocg,
  author = {de Berg, Sarita and van Kreveld, Marc and Staals, Frank},
  title = {The complexity of geodesic spanners},
  journal = {Abstr. 38th European Workshop on Computational Geometry (EuroCG)},
  year = {2022},
  location = {Perugia, Italy},
  numpages = {7},
  category = {geodesic},
  project = {geodesic_spanners2023},
}