Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.05357 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916169351430144 |
|---|---|
| author | Chan, Timothy M. Huang, Zhengcheng |
| author_facet | Chan, Timothy M. Huang, Zhengcheng |
| contents | We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types of geometric objects in 2D. Our data structures can answer connectivity queries between two objects, as well as "global" connectivity queries (e.g., deciding whether the entire graph is connected). Previously, the data structure by Afshani and Chan (ESA'06) achieved such bounds only in the special case of axis-aligned line segments or rectangles but did not work for arbitrary line segments or disks, whereas the data structures by Chan, Pătraşcu and Roditty (FOCS'08) worked for more general classes of geometric objects but required $n^{Ω(1)}$ query time and could not handle global connectivity queries. Specifically, we obtain new data structures with $O(1)$ query time and amortized update time near $n^{4/5}$, $n^{7/8}$, and $n^{20/21}$ for axis-aligned line segments, disks, and arbitrary line segments respectively. Besides greatly reducing the query time, our data structures also improve the previous update times for axis-aligned line segments by Afshani and Chan (from near $n^{10/11}$ to $n^{4/5}$) and for disks by Chan, Pătraşcu, and Roditty (from near $n^{20/21}$ to $n^{7/8}$). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05357 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dynamic Geometric Connectivity in the Plane with Constant Query Time Chan, Timothy M. Huang, Zhengcheng Computational Geometry We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types of geometric objects in 2D. Our data structures can answer connectivity queries between two objects, as well as "global" connectivity queries (e.g., deciding whether the entire graph is connected). Previously, the data structure by Afshani and Chan (ESA'06) achieved such bounds only in the special case of axis-aligned line segments or rectangles but did not work for arbitrary line segments or disks, whereas the data structures by Chan, Pătraşcu and Roditty (FOCS'08) worked for more general classes of geometric objects but required $n^{Ω(1)}$ query time and could not handle global connectivity queries. Specifically, we obtain new data structures with $O(1)$ query time and amortized update time near $n^{4/5}$, $n^{7/8}$, and $n^{20/21}$ for axis-aligned line segments, disks, and arbitrary line segments respectively. Besides greatly reducing the query time, our data structures also improve the previous update times for axis-aligned line segments by Afshani and Chan (from near $n^{10/11}$ to $n^{4/5}$) and for disks by Chan, Pătraşcu, and Roditty (from near $n^{20/21}$ to $n^{7/8}$). |
| title | Dynamic Geometric Connectivity in the Plane with Constant Query Time |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2402.05357 |