Dynamic connectivity for axis-parallel rectangles

DOI10.1007/s00453-008-9234-7zbMath1184.68196OpenAlexW2082803170MaRDI QIDQ1016519

Timothy M. Chan, Peyman Afshani

Publication date: 6 May 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9234-7

zbMATH Keywords

data structurescomputational geometrydynamic data structuresdynamic connectivity

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (1)

On pseudo-disk hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Lower bounds for fully dynamic connectivity problems in graphs
• Applications of random sampling in computational geometry. II
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Near-optimal fully-dynamic graph connectivity
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Dynamic Subgraph Connectivity with Geometric Applications
• Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n ² barrier
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Semi-Online Maintenance of Geometric Optima and Measures
• Decremental Dynamic Connectivity
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Logarithmic Lower Bounds in the Cell-Probe Model
• A fully dynamic algorithm for maintaining the transitive closure
• Algorithms for generalized halfspace range searching and other intersection searching problems

This page was built for publication: Dynamic connectivity for axis-parallel rectangles