Name
Abstract | ||
|---|---|---|
We present efficient data structures for problems on unit discs and arcs of their boundary in the plane. (i) We give an output-sensitive algorithm for the dynamic maintenance of the union of $n$ unit discs under insertions in $O(k log^2 n)$ update time and $O(n)$ space, where $k$ is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. (ii) As part of the solution of (i) we devise a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines, which we believe is of independent interest. The structure has $O(log^2 n)$ update time and $O(log n)$ vertical ray shooting query time. To achieve this performance, we devise a new algorithm for finding the intersection between two lower envelopes of pseudo-lines in $O(log n)$ time, using emph{tentative} binary search; the lower envelopes are special in that at $x=-infty$ any pseudo-line contributing to the first envelope lies below every pseudo-line contributing to the second envelope. (iii) We also present a dynamic range searching structure for a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), where the ranges are unit discs, with $O(n log n)$ preprocessing time, $O(n^{1/2+varepsilon} + ell)$ query time and $O(log^2 n)$ amortized update time, where $ell$ is the size of the output and for any $varepsilonu003e0$. The structure requires $O(n)$ storage space. |
Year | Venue | Field |
|---|---|---|
2019 | arXiv: Computational Geometry | Discrete mathematics,Computer science |
DocType | Volume | Citations |
Journal | abs/1903.10943 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Ravid Cohen | 2 | 0 | 1.01 |
| Dan Halperin | 3 | 1291 | 105.20 |
| Wolfgang Mulzer | 4 | 257 | 36.08 |