A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
| Autor: | Gudmundsson, Joachim, Seybold, Martin P. |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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]. It also shows that history-based RIC circumvents a lower bound on runtime tail estimates of conflict-graph RICs [Sen; STACS 2019]. Comment: New high probability bound in Section 4.1; Further applications in Section 5 |
| Databáze: | arXiv |
| Externí odkaz: |
|