Dynamic connectivity in disk graphs

DOI10.1007/S00454-023-00621-XzbMATH Open1530.05104arXiv2106.14935OpenAlexW3174710476MaRDI QIDQ6145677FDOQ6145677

Authors: Alexander Baumann, Haim Kaplan, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty, Paul Seiferth 

Publication date: 9 January 2024

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Let $S$ be a set of $n$ sites, each associated with a point in $mathbb{R}^2$ and a radius $r_s$ and let $mathcalD(S)$ be the disk graph on $S$. We consider the problem of designing data structures that maintain the connectivity structure of $mathcalD(S)$ while allowing the insertion and deletion of sites. For unit disk graphs we describe a data structure that has $O(lo{g}^{2}n)$ amortized update time and $O((logn)/(loglogn))$ amortized query time. For disk graphs where the ratio $Psi$ between the largest and smallest radius is bounded, we consider the decremental and the incremental case separately, in addition to the fully dynamic case. In the fully dynamic case we achieve amortized $O(Psilambd{a}_6(logn)lo{g}^{9}n)$ update time and $O(logn)$ query time, where $lambd{a}_s(n)$ is the maximum length of a Davenport-Schinzel sequence of order $s$ on $n$ symbols. This improves the update time of the currently best known data structure by a factor of $Psi$ at the cost of an additional $O(loglogn)$ factor in the query time. In the incremental case we manage to achieve a logarithmic dependency on $Psi$ with a data structure with $O(alpha(n))$ query and $O(logPsilambd{a}_6(logn)lo{g}^{9}n)$ update time. For the decremental setting we first develop a new dynamic data structure that allows us to maintain two sets $B$ and $P$ of disks, such than at a deletion of a disk from $B$ we can efficiently report all disks in $P$ that no longer intersect any disk of $B$. Having this data structure at hand, we get decremental data structures with an amortized query time of $O((logn)/(loglogn))$ supporting $m$ deletions in $O((nlo{g}^{5}n+mlo{g}^{9}n)lambd{a}_6(logn)+nlogPsilo{g}^{4}n)$ overall time for bounded radius ratio $Psi$ and $O((nlo{g}^{6}n+mlo{g}^{10}n)lambd{a}_6(logn))$ for general disk graphs.

Full work available at URL: https://arxiv.org/abs/2106.14935

Recommendations

• Dynamic connectivity in disk graphs
• Kinetic connectivity for unit disks
• Dynamic connectivity: connecting to networks and geometry
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications

zbMATH Keywords

connectivitydisk graphslower envelopes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Connectivity (05C40)

Cites Work

• Introduction to algorithms.
• A data structure for dynamic trees
• Title not available (Why is that?)
• Computational geometry. Algorithms and applications.
• A sweepline algorithm for Voronoi diagrams
• A topological approach to dynamic graph connectivity
• Maintenance of configurations in the plane
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Optimal Point Location in a Monotone Subdivision
• Decomposable searching problems I. Static-to-dynamic transformation
• Faster kinetic heaps and their use in broadcast scheduling. (Extended abstract)
• Geometric approximation algorithms
• Shortest paths in intersection graphs of unit disks
• Biased Search Trees
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• On range searching with semialgebraic sets
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• Euclidean minimum spanning trees and bichromatic closest pairs
• Near-optimal fully-dynamic graph connectivity
• Dynamic planar convex hull operations in near-logarithmic amortized time
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Dynamic graph connectivity in polylogarithmic worst case time
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Dynamic planar point location with sub-logarithmic local updates
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Faster deterministic fully-dynamic graph connectivity
• Dynamic connectivity: connecting to networks and geometry
• Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent
• Spanners for directed transmission graphs
• Dynamic geometric data structures via shallow cuttings
• An algorithmic framework for the single source shortest path problem with applications to disk graphs
• Triangles and girth in disk graphs and transmission graphs
• Title not available (Why is that?)
• Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions

Cited In (2)

• Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead
• Dynamic connectivity in disk graphs

This page was built for publication: Dynamic connectivity in disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145677)