  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].
