Document Open Access Logo

Online Euclidean Spanners

Authors Sujoy Bhore , Csaba D. Tóth

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.16.pdf
  • Filesize: 1.01 MB
  • 19 pages

Document Identifiers

Author Details

Sujoy Bhore
  • Indian Institute of Science Education and Research, Bhopal, India
Csaba D. Tóth
  • California State University Northridge, Los Angeles, CA, USA
  • Tufts University, Medford, MA, USA

Funding

  • Tóth, Csaba D.: Research was partially supported by the NSF award DMS-1800734.

Cite As Get BibTex

Sujoy Bhore and Csaba D. Tóth. Online Euclidean Spanners. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.16

Abstract

In this paper, we study the online Euclidean spanners problem for points in ℝ^d. Given a set S of n points in ℝ^d, a t-spanner on S is a subgraph of the underlying complete graph G = (S,binom(S,2)), that preserves the pairwise Euclidean distances between points in S to within a factor of t, that is the stretch factor. Suppose we are given a sequence of n points (s₁,s₂,…, s_n) in ℝ^d, where point s_i is presented in step i for i = 1,…, n. The objective of an online algorithm is to maintain a geometric t-spanner on S_i = {s₁,…, s_i} for each step i. The algorithm is allowed to add new edges to the spanner when a new point is presented, but cannot remove any edge from the spanner. The performance of an online algorithm is measured by its competitive ratio, which is the supremum, over all sequences of points, of the ratio between the weight of the spanner constructed by the algorithm and the weight of an optimum spanner. Here the weight of a spanner is the sum of all edge weights. 
First, we establish a lower bound of Ω(ε^{-1}log n / log ε^{-1}) for the competitive ratio of any online (1+ε)-spanner algorithm, for a sequence of n points in 1-dimension. We show that this bound is tight, and there is an online algorithm that can maintain a (1+ε)-spanner with competitive ratio O(ε^{-1}log n / log ε^{-1}). Next, we design online algorithms for sequences of points in ℝ^d, for any constant d ≥ 2, under the L₂ norm. We show that previously known incremental algorithms achieve a competitive ratio O(ε^{-(d+1)}log n). However, if the algorithm is allowed to use additional points (Steiner points), then it is possible to substantially improve the competitive ratio in terms of ε. We describe an online Steiner (1+ε)-spanner algorithm with competitive ratio O(ε^{(1-d)/2} log n). As a counterpart, we show that the dependence on n cannot be eliminated in dimensions d ≥ 2. In particular, we prove that any online spanner algorithm for a sequence of n points in ℝ^d under the L₂ norm has competitive ratio Ω(f(n)), where lim_{n → ∞}f(n) = ∞. Finally, we provide improved lower bounds under the L₁ norm: Ω(ε^{-2}/log ε^{-1}) in the plane and Ω(ε^{-d}) in ℝ^d for d ≥ 3.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
  • Mathematics of computing → Paths and connectivity problems
  • Theory of computation → Computational geometry
Keywords
  • Geometric spanner
  • (1+ε)-spanner
  • minimum weight
  • online algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. A general approach to online network optimization problems. ACM Transactions on Algorithms (TALG), 2(4):640-660, 2006. Google Scholar
  2. Noga Alon and Yossi Azar. On-line Steiner trees in the Euclidean plane. Discrete & Computational Geometry, 10:113-121, 1993. Google Scholar
  3. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81-100, 1993. Google Scholar
  4. Sunil Arya, David M Mount, and Michiel Smid. Randomized and deterministic algorithms for geometric spanners of small diameter. In Proc. 35th IEEE Symposium on Foundations of Computer Science (FOCS), pages 703-712, 1994. Google Scholar
  5. Sunil Arya and Michiel Smid. Efficient construction of a bounded-degree spanner with low weight. Algorithmica, 17(1):33-54, 1997. Google Scholar
  6. Baruch Awerbuch, Yossi Azar, and Yair Bartal. On-line generalized Steiner problem. Theoretical Computer Science, 324(2-3):313-324, 2004. Google Scholar
  7. Baruch Awerbuch, Alan E. Baratz, and David Peleg. Cost-sensitive analysis of communication protocols. In Proc. 9th ACM Symposium on Principles of Distributed Computing (PODC), pages 177-187, 1990. Google Scholar
  8. Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms, 8(4):35:1-35:51, 2012. Google Scholar
  9. Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New techniques and fine-grained hardness for dynamic near-additive spanners. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1836-1855, 2021. Google Scholar
  10. Piotr Berman and Chris Coulston. On-line algorithms for steiner tree problems. In Proc. 29th ACM Symposium on Theory of Computing (STOC), pages 344-353, 1997. Google Scholar
  11. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1899-1918, 2019. Google Scholar
  12. Sujoy Bhore and Csaba D. Tóth. Light Euclidean Steiner spanners in the plane. In Proc. 37th International Symposium on Computational Geometry (SoCG), volume 189 of LIPIcs, pages 31:1-17. Schloss Dagstuhl, 2021. Google Scholar
  13. Sujoy Bhore and Csaba D. Tóth. On Euclidean Steiner (1+ε)-spanners. In Proc. 38th Symposium on Theoretical Aspects of Computer Science (STACS), volume 187 of LIPIcs, pages 13:1-13:16. Schloss Dagstuhl, 2021. Google Scholar
  14. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  15. Prosenjit Bose, Joachim Gudmundsson, and Pat Morin. Ordered theta graphs. Computational Geometry, 28(1):11-18, 2004. Google Scholar
  16. Prosenjit Bose and Michiel H. M. Smid. On plane geometric spanners: A survey and open problems. Comput. Geom., 46(7):818-830, 2013. Google Scholar
  17. Paul B. Callahan. Optimal parallel all-nearest-neighbors using the well-separated pair decomposition. In Proc. 34th IEEE Symposium on Foundations of Computer Science (FOCS), pages 332-340, 1993. Google Scholar
  18. Paul B. Callahan and S. Rao Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Vijaya Ramachandran, editor, Proc. 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 291-300, 1993. Google Scholar
  19. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67-90, 1995. Google Scholar
  20. Paz Carmi and Lilach Chaitman-Yerushalmi. Minimum weight Euclidean t-spanner is NP-hard. Journal of Discrete Algorithms, 22:30-42, 2013. Google Scholar
  21. Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones. On locality-sensitive orderings and their applications. SIAM J. Comput., 49(3):583-600, 2020. Google Scholar
  22. L. Paul Chew. There is a planar graph almost as good as the complete graph. In Proc. 2nd Symposium on Computational Geometry (SoCG), pages 169-177. ACM Press, 1986. Google Scholar
  23. L. Paul Chew. There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci., 39(2):205-219, 1989. Google Scholar
  24. Kenneth L. Clarkson. Approximation algorithms for shortest path motion planning. In Proc. 19th ACM Symposium on Theory of Computing (STOC), pages 56-65, 1987. Google Scholar
  25. Gautam Das, Paul Heffernan, and Giri Narasimhan. Optimally sparse spanners in 3-dimensional Euclidean space. In Proc. 9th Symposium on Computational Geometry (SoCG), pages 53-62. ACM Press, 1993. Google Scholar
  26. Gautam Das, Giri Narasimhan, and Jeffrey S. Salowe. A new way to weigh malnourished Euclidean graphs. In Proc. 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 215-222, 1995. Google Scholar
  27. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational Geometry: Algorithms and Applications. Springer, 3 edition, 2008. Google Scholar
  28. Michael Elkin and Shay Solomon. Steiner shallow-light trees are exponentially lighter than spanning ones. SIAM Journal on Computing, 44(4):996-1025, 2015. Google Scholar
  29. John Fischer and Sariel Har-Peled. Dynamic well-separated pair decomposition made easy. In Proc. 17th Canadian Conference on Computational Geometry (CCCG), pages 235-238, 2005. Google Scholar
  30. Jie Gao, Leonidas J. Guibas, and An Nguyen. Deformable spanners and applications. Comput. Geom., 35(1-2):2-19, 2006. Google Scholar
  31. Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient regression in metric spaces via approximate Lipschitz extension. IEEE Transactions on Information Theory, 63(8):4838-4849, 2017. Google Scholar
  32. Lee-Ad Gottlieb and Liam Roditty. An optimal dynamic spanner for doubling metric spaces. In Proc. 16th European Symposium on Algorithms (ESA), volume 5193 of LNCS, pages 478-489. Springer, 2008. Google Scholar
  33. Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: Maintaining a constant-competitive Steiner tree online. SIAM Journal on Computing, 45(1):1-28, 2016. Google Scholar
  34. Joachim Gudmundsson and Christian Knauer. Dilation and detours in geometric networks. In Teofilo F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics, volume 2. Chapman and Hall/CRC, 2nd edition, 2018. Google Scholar
  35. Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan. Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput., 31(5):1479-1500, 2002. Google Scholar
  36. Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, and Michiel Smid. Approximate distance oracles for geometric spanners. ACM Transactions on Algorithms (TALG), 4(1):1-34, 2008. Google Scholar
  37. Mohammad Taghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi. Online node-weighted Steiner forest and extensions via disk paintings. In Porc. 54th IEEE Symposium on Foundations of Computer Science (FOCS), pages 558-567, 2013. Google Scholar
  38. Sariel Har-Peled. Geometric Approximation Algorithms, volume 173 of Mathematical Surveys and Monographs. AMS, Providence, RI, 2011. Google Scholar
  39. Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369-384, 1991. Google Scholar
  40. J. Mark Keil. Approximating the complete Euclidean graph. In Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT), volume 318 of LNCS, pages 208-213. Springer, 1988. Google Scholar
  41. Samir Khuller, Balaji Raghavachari, and Neal E. Young. Balancing minimum spanning and shortest path trees. In Proc. 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 243-250, 1993. Google Scholar
  42. Hung Le and Shay Solomon. Truly optimal Euclidean spanners. In Proc. 60th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1078-1100, 2019. Google Scholar
  43. Hung Le and Shay Solomon. Light Euclidean spanners with Steiner points. In Proc. 28th European Symposium on Algorithms (ESA), volume 173 of LIPIcs, pages 67:1-67:22. Schloss Dagstuhl, 2020. Google Scholar
  44. Hung Le and Shay Solomon. A unified and fine-grained approach for light spanners. CoRR, abs/2008.10582, 2020. URL: http://arxiv.org/abs/2008.10582.
  45. Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. SIAM Journal on Computing, 45(3):859-880, 2016. Google Scholar
  46. Joseph Naor, Debmalya Panigrahi, and Mohit Singh. Online node-weighted Steiner tree and related problems. In Proc. 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 210-219, 2011. Google Scholar
  47. Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, 2007. Google Scholar
  48. Satish B. Rao and Warren D. Smith. Approximating geometrical graphs via “spanners” and “banyans”. In Proc. 13th ACM Symposium on Theory of Computing (STOC), pages 540-550, 1998. Google Scholar
  49. Liam Roditty. Fully dynamic geometric spanners. Algorithmica, 62(3-4):1073-1087, 2012. Google Scholar
  50. Christian Schindelhauer, Klaus Volbert, and Martin Ziegler. Geometric spanners with applications in wireless networks. Comput. Geom., 36(3):197-214, 2007. Google Scholar
  51. Michiel H. M. Smid. The well-separated pair decomposition and its applications. In Teofilo F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics, volume 2. Chapman and Hall/CRC, 2nd edition, 2018. Google Scholar
  52. Shay Solomon. Euclidean Steiner shallow-light trees. J. Comput. Geom., 6(2):113-139, 2015. Google Scholar
  53. Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721-736, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact