A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917965031538688 |
|---|---|
| author | Gudmundsson, Joachim Seybold, Martin P. |
| author_facet | Gudmundsson, Joachim Seybold, Martin P. |
| contents | The Randomized Incremental Construction (RIC) of search DAGs for point location in planar subdivisions, nearest-neighbor search in 2D points, and extreme point search in 3D convex hulls, are well known to take ${\cal O}(n \log n)$ expected time for structures of ${\cal O}(n)$ expected size. Moreover, searching takes w.h.p. ${\cal O}(\log n)$ comparisons in the first and w.h.p. ${\cal O}(\log^2 n)$ comparisons in the latter two DAGs. However, the expected depth of the DAGs and high probability bounds for their size are unknown.
Using a novel analysis technique, we show that the three DAGs have w.h.p. i) a size of ${\cal O}(n)$, ii) a depth of ${\cal O}(\log n)$, and iii) a construction time of ${\cal O}(n \log n)$. One application of these new and improved results are \emph{remarkably simple} Las Vegas verifiers to obtain search DAGs with optimal worst-case bounds. This positively answers the conjectured logarithmic search cost in the DAG of Delaunay triangulations [Guibas et al.; ICALP 1990] and a conjecture on the depth of the DAG of Trapezoidal subdivisions [Hemmer et al.; ESA 2012]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2101_04914 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures Gudmundsson, Joachim Seybold, Martin P. Computational Geometry Data Structures and Algorithms F.2.2 The Randomized Incremental Construction (RIC) of search DAGs for point location in planar subdivisions, nearest-neighbor search in 2D points, and extreme point search in 3D convex hulls, are well known to take ${\cal O}(n \log n)$ expected time for structures of ${\cal O}(n)$ expected size. Moreover, searching takes w.h.p. ${\cal O}(\log n)$ comparisons in the first and w.h.p. ${\cal O}(\log^2 n)$ comparisons in the latter two DAGs. However, the expected depth of the DAGs and high probability bounds for their size are unknown. Using a novel analysis technique, we show that the three DAGs have w.h.p. i) a size of ${\cal O}(n)$, ii) a depth of ${\cal O}(\log n)$, and iii) a construction time of ${\cal O}(n \log n)$. One application of these new and improved results are \emph{remarkably simple} Las Vegas verifiers to obtain search DAGs with optimal worst-case bounds. This positively answers the conjectured logarithmic search cost in the DAG of Delaunay triangulations [Guibas et al.; ICALP 1990] and a conjecture on the depth of the DAG of Trapezoidal subdivisions [Hemmer et al.; ESA 2012]. |
| title | A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures |
| topic | Computational Geometry Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2101.04914 |