Dynamic Connectivity in Disk Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916230184566784 |
|---|---|
| author | Baumann, Alexander Kaplan, Haim Klost, Katharina Knorr, Kristin Mulzer, Wolfgang Roditty, Liam Seiferth, Paul |
| author_facet | Baumann, Alexander Kaplan, Haim Klost, Katharina Knorr, Kristin Mulzer, Wolfgang Roditty, Liam Seiferth, Paul |
| contents | Let $S$ be a set of $n$ sites in the plane, so that every site $s \in S$ has an associated radius $r_s > 0$. Let $\mathcal{D}(S)$ be the disk intersection graph defined by $S$, i.e., the graph with vertex set $S$ and an edge between two distinct sites $s, t \in S$ if and only if the disks with centers $s$, $t$ and radii $r_s$, $r_t$ intersect.Our goal is to design data structures that maintain the connectivity structure of $\mathcal{D}(S)$ as sites are inserted and/or deleted in $S$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_14935 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Dynamic Connectivity in Disk Graphs Baumann, Alexander Kaplan, Haim Klost, Katharina Knorr, Kristin Mulzer, Wolfgang Roditty, Liam Seiferth, Paul Computational Geometry Data Structures and Algorithms Let $S$ be a set of $n$ sites in the plane, so that every site $s \in S$ has an associated radius $r_s > 0$. Let $\mathcal{D}(S)$ be the disk intersection graph defined by $S$, i.e., the graph with vertex set $S$ and an edge between two distinct sites $s, t \in S$ if and only if the disks with centers $s$, $t$ and radii $r_s$, $r_t$ intersect.Our goal is to design data structures that maintain the connectivity structure of $\mathcal{D}(S)$ as sites are inserted and/or deleted in $S$. |
| title | Dynamic Connectivity in Disk Graphs |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2106.14935 |