Dynamic connectivity for axis-parallel rectangles

DOI10.1007/S00453-008-9234-7MaRDI QIDQ1016519zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Timothy M. Chan

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

computational geometrydata structuresdynamic data structuresdynamic connectivity

Mathematics Subject Classification ID

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

Recommendations

• Dynamic Connectivity for Axis-Parallel Rectangles
• Semi-dynamic connectivity in the plane
• Simplified kinetic connectivity for rectangles and hypercubes
• Dynamic connectivity: connecting to networks and geometry
• Dynamic Subgraph Connectivity with Geometric Applications
• Fully Dynamic Algorithms for 2-Edge Connectivity
• Static and dynamic parallel computation of connected components
• Fully dynamic 2-edge-connectivity in planar graphs
• A topological approach to dynamic graph connectivity

Cites work

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

Cited in

(4)

• On pseudo-disk hypergraphs
• Dynamic Connectivity for Axis-Parallel Rectangles
• Dynamic connectivity: connecting to networks and geometry
• Simplified kinetic connectivity for rectangles and hypercubes

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

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