Dynamic connectivity in disk graphs

DOI10.1007/S00454-023-00621-XMaRDI QIDQ6145677zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

connectivitydisk graphslower envelopes

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(5)

• Maintaining the union of unit discs under insertions with near-optimal overhead
• Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead
• Dynamic connectivity in disk graphs
• Single-source shortest path problem in weighted disk graphs
• An optimal algorithm for shortest paths in unweighted 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)