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].
Categories: cs.CG cs.DS