Document Open Access Logo

Computing the Minimum Bottleneck Moving Spanning Tree

Authors Haitao Wang, Yiming Zhao

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.82.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Author Details

Haitao Wang
  • Department of Computer Science, Utah State University, Logan, UT, USA
Yiming Zhao
  • Department of Computer Science, Utah State University, Logan, UT, USA

Funding

This research was supported in part by NSF under Grant CCF-2005323.

Cite As Get BibTex

Haitao Wang and Yiming Zhao. Computing the Minimum Bottleneck Moving Spanning Tree. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.82

Abstract

Given a set P of n points that are moving in the plane, we consider the problem of computing a spanning tree for these moving points that does not change its combinatorial structure during the point movement. The objective is to minimize the bottleneck weight of the spanning tree (i.e., the largest Euclidean length of all edges) during the whole movement. The problem was solved in O(n²) time previously [Akitaya, Biniaz, Bose, De Carufel, Maheshwari, Silveira, and Smid, WADS 2021]. In this paper, we present a new algorithm of O(n^{4/3} log³ n) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
Keywords
  • minimum spanning tree
  • moving points
  • unit-disk range emptiness query
  • dynamic data structure

Metrics

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

Related Versions

References

  1. Pankaj K. Agarwal and Jirí Matoušek. Dynamic half-space range reporting and its applications. Algorithmica, 13(4):325-345, 1995. Google Scholar
  2. Hugo A. Akitaya, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, Luís Fernando Schultz Xavier da Silveira, and Michiel Smid. The minimum moving spanning tree problem. In Proceedings of the 17th Workshop on Algorithms and Data Structures (WADS), pages 15-28, 2021. Google Scholar
  3. Mikhail J. Atallah. Dynamic computational geometry. In Proceedings of 24th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 92-99, 1983. Google Scholar
  4. Julien Basch, Leonidas J. Guibas, and John Hershberger. Data structures for mobile data. Journal of Algorithms, 31:1-28, 1999. Google Scholar
  5. Gerth S. Brodal and Riko Jacob. Dynamic planar convex hull. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 617-626, 2002. Google Scholar
  6. Sergio Cabello and Miha Jejčič. Shortest paths in intersection graphs of unit disks. Computational Geometry: Theory and Applications, 48(4):360-367, 2015. Google Scholar
  7. Paolo M. Camerini. The min-max spanning tree problem and some extensions. Information Processing Letters, 7:10-14, 1978. Google Scholar
  8. Timothy M. Chan. Dynamic planar convex hull operations in near-logarithmaic amortized time. Journal of the ACM, 48:1-12, 2001. Google Scholar
  9. Timothy M. Chan. A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. Journal of the ACM, 57:16:1-16:15, 2010. Google Scholar
  10. Timothy M. Chan. Optimal partition trees. Discrete and Computational Geometry, 47:661-690, 2012. Google Scholar
  11. Timothy M. Chan. Dynamic geometric data structures via shallow cuttings. Discrete and Computational Geometry, 64:1235-1252, 2020. Google Scholar
  12. Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), pages 24:1-24:13, 2016. Google Scholar
  13. Timothy M. Chan and Dimitrios Skrepetos. Approximate shortest paths and distance oracles in weighted unit-disk graphs. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG), pages 24:1-24:13, 2018. Google Scholar
  14. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete mathematics, 86:165-177, 1990. Google Scholar
  15. David Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete and Computational Geometry, 13:111-122, 1995. Google Scholar
  16. Jie Gao and Li Zhang. Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM Journal on Computing, 35(1):151-169, 2005. Google Scholar
  17. John Hershberger and Subhash Suri. Applications of a semi-dynamic convex hull algorithm. BIT Numerical Mathematics, 32(2):249-267, 1992. Google Scholar
  18. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2495-2504, 2017. Google Scholar
  19. Matthew J. Katz and Micha Sharir. An expander-based approach to geometric optimization. SIAM Journal on Computing, 26(5):1384-1408, 1997. Google Scholar
  20. Jirí Matoušek. Efficient partition trees. Discrete and Computational Geometry, 8:315-334, 1992. Google Scholar
  21. Jirí Matoušek. Range searching with efficient hierarchical cuttings. Discrete and Computational Geometry, 10:157-182, 1993. Google Scholar
  22. Tomomi Matsui. Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In Proceedings of the Japanese Conference on Discrete and Computational Geometry (JCDCG), pages 194-200, 1998. Google Scholar
  23. Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. Journal of Computer System Sciences, 23(2):166-204, 1981. Google Scholar
  24. Franco P. Preparata and Michael I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985. Google Scholar
  25. Zahed Rahmati and Alireza Zarei. Kinetic Euclidean minimum spanning tree in the plane. Journal of Discrete Algorithms, 16:2-11, 2012. Google Scholar
  26. Haitao Wang. Unit-disk range searching and applications. In Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 32:1-32:17, 2022. Google Scholar
  27. Haitao Wang and Jie Xue. Near-optimal algorithms for shortest paths in weighted unit-disk graphs. Discrete and Computational Geometry, 64:1141-1166, 2020. Google Scholar
  28. Haitao Wang and Yiming Zhao. An optimal algorithm for L₁ shortest paths in unit-disk graphs. In Proceedings of the 33rd Canadian Conference on Computational Geometry (CCCG), pages 211-218, 2021. Google Scholar
  29. Haitao Wang and Yiming Zhao. Reverse shortest path problem for unit-disk graphs. In Proceedings of the 17th International Symposium of Algorithms and Data Structures (WADS), pages 655-668, 2021. Google Scholar
  30. Haitao Wang and Yiming Zhao. Reverse shortest path problem for weighted unit-disk graphs. In Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM), pages 135-146, 2022. 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