Abstract

A classical problem in computational geometry and graph algorithms is: given a dynamic set \(\mathcal{S}\) of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of \(\mathcal{S}\). Previous papers studied the setting where, before the updates, the data structure receives some parameter \(P\). Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range \([\frac{1}{P}, 1]\). As a consequence of that prerequisite, the aspect ratio \(\psi\) (i.e. the ratio between the largest and smallest diameter) of the disks would at all times satisfy \(\psi \leq P\). The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses \(O(Pn)\) space and that has amortized \(O(P \log^4 n)\) expected amortized update time. Connectivity queries between disks are supported in \(O(\log n / \log \log n)\) time.

In the dynamic setting, one wishes for a more flexible data structure in which disks of any diameter may arrive and leave, independent of their diameter, changing the aspect ratio freely. Ideally, the aspect ratio should merely be part of the analysis. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio \(\psi\), as opposed to some previously given maximum \(P\). Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When \(n\) is the number of squares and \(\psi\) is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in \(O(\log n / \log \log n)\) time. We can update connectivity information in \(O(\psi \log^4 n + \log^6 n)\) amortized time. We also improve space usage from \(O(P \cdot n \log n)\) to \(O(n \log^3 n \log \psi)\) — while generalizing to a fully-adaptive aspect ratio — which yields a space usage that is near-linear in \(n\) for any polynomially bounded \(\psi\).

Corresponding Publications

Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

Ivor van der Hoog, André Nusser, Eva Rotenberg, Frank Staals

Proc. 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), 2024

Download Local Copy View Slides Export Citation

@inproceedings{squareconnectivity2024,
  author = {van der Hoog, Ivor and Nusser, Andr{\'{e}} and Rotenberg, Eva and Staals, Frank},
  title = {Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs},
  booktitle = {Proc. 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  year = {2024},
  location = {Bratislava, Slovakia},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  pages = {63:1--63:17},
  isbn = {978-3-95977-335-5},
  issn = {1868-8969},
  volume = {306},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  category = {datastructures},
  url = {https://doi.org/10.4230/LIPIcs.MFCS.2024.63},
  doi = {10.4230/LIPIcs.MFCS.2024.63},
  keywords = {Computational geometry, planar geometry, data structures, geometric intersection graphs, fully-dynamic algorithms},
}