A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures

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 (n log n) expected time for structures of (n) expected size. Moreover, searching takes w.h.p. (log n) comparisons in the first and w.h.p. (log2 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 (n), ii) a depth of (log n), and iii) a construction time of (n log n). One application of these new and improved results are 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].