Cover Image

Dynamic Geometric Connectivity in the Plane with Constant Query Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chan, Timothy M., Huang, Zhengcheng
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
by: Bhore, Sujoy, et al.
Published: (2025)

Fully Dynamic Geometric Vertex Cover and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
by: Chan, Timothy M., et al.
Published: (2024)

Triangulating a Polygon with Holes in Optimal (Deterministic) Time
by: Chan, Timothy M.
Published: (2026)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Constant Workspace Algorithms for Computing Relative Hulls in the Plane
by: Chhabra, Himanshu, et al.
Published: (2024)

Enclosing Points with Geometric Objects
by: Chan, Timothy M., et al.
Published: (2024)

Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
by: Chan, Timothy M., et al.
Published: (2026)

Convex Polygon Containment: Improving Quadratic to Near Linear Time
by: Chan, Timothy M., et al.
Published: (2024)

Plane Strong Connectivity Augmentation
by: Bessy, Stéphane, et al.
Published: (2025)

Shortest Path Separators in Unit Disk Graphs
by: Harb, Elfarouk, et al.
Published: (2024)

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation
by: Chan, Timothy M., et al.
Published: (2025)

A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D
by: Buchin, Kevin, et al.
Published: (2026)

Further Connectivity Results on Plane Spanning Path Reconfiguration
by: Boucard, Valentino, et al.
Published: (2024)

Computing the Girth of a Segment Intersection Graph
by: Chan, Timothy M., et al.
Published: (2026)

On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects
by: Chan, Timothy M., et al.
Published: (2024)

On Computing Vertex Connectivity of 1-Plane Graphs
by: Biedl, Therese, et al.
Published: (2022)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2025)

Generalize cross-ratios in n-dimensional Plane-Based Geometric Algebra
by: Harquin, Enzo, et al.
Published: (2026)

On $k$-Plane Insertion into Plane Drawings
by: Katheder, Julia, et al.
Published: (2024)

On the Connectivity of the Flip Graph of Plane Spanning Paths
by: Kleist, Linda, et al.
Published: (2024)

Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

Dynamic and Streaming Algorithms for Union Volume Estimation
by: Bhore, Sujoy, et al.
Published: (2026)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
by: Chan, Timothy M., et al.
Published: (2026)

Incremental Planar Nearest Neighbor Queries with Optimal Query Time
by: Iacono, John, et al.
Published: (2025)

Long Plane Trees
by: Cabello, Sergio, et al.
Published: (2021)

Untangling Segments in the Plane
by: da Fonseca, Guilherme D., et al.
Published: (2025)

Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs
by: van der Hoog, Ivor, et al.
Published: (2024)

Undecidability of Translational Tiling of the Plane with Four Tiles
by: Yang, Chao, et al.
Published: (2025)

Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
by: Yang, Chao, et al.
Published: (2025)

Minimum Plane Bichromatic Spanning Trees
by: Akitaya, Hugo A., et al.
Published: (2024)

An Improved Bound for Plane Covering Paths
by: Akitaya, Hugo A., et al.
Published: (2025)

A New Approach in Plane Kinematics
by: Goessner, Stefan
Published: (2026)

A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets
by: Aichholzer, Oswin, et al.
Published: (2025)

Sweeping Arrangements of Non-Piercing Curves in Plane
by: Dalal, Suryendu, et al.
Published: (2024)

Covering the Euclidean Plane by a Pair of Trees
by: Le, Hung, et al.
Published: (2025)

Dynamic Connectivity in Disk Graphs
by: Baumann, Alexander, et al.
Published: (2021)

On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane
by: Edelsbrunner, Herbert, et al.
Published: (2022)

Deciding Connectivity in Symmetric Semi-Algebraic Sets
by: Riener, Cordian., et al.
Published: (2025)