Dynamic connectivity in disk graphs
From MaRDI portal
Publication:6145677
DOI10.1007/s00454-023-00621-xzbMath1530.05104arXiv2106.14935OpenAlexW3174710476MaRDI QIDQ6145677
Alexander Baumann, Liam Roditty, Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Paul Seiferth, Kristin Knorr
Publication date: 9 January 2024
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2106.14935
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Connectivity (05C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Preprocessing imprecise points for Delaunay triangulation: simplified and extended
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- A sweepline algorithm for Voronoi diagrams
- A topological approach to dynamic graph connectivity
- Maintenance of configurations in the plane
- Euclidean minimum spanning trees and bichromatic closest pairs
- On range searching with semialgebraic sets
- Dynamic Euclidean minimum spanning trees and extrema of binary functions
- A data structure for dynamic trees
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Dynamic geometric data structures via shallow cuttings
- Shortest paths in intersection graphs of unit disks
- Dynamic Planar Point Location with Sub-logarithmic Local Updates
- Dynamic planar convex hull operations in near-logarithmic amortized time
- Dynamic Connectivity: Connecting to Networks and Geometry
- Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent
- Near-optimal fully-dynamic graph connectivity
- A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
- Intersection and Closest-Pair Problems for a Set of Planar Discs
- Biased Search Trees
- Optimal Point Location in a Monotone Subdivision
- Decomposable searching problems I. Static-to-dynamic transformation
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
- Spanners for Directed Transmission Graphs
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster Deterministic Fully-Dynamic Graph Connectivity
- Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
- An algorithmic framework for the single source shortest path problem with applications to disk graphs
