English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The Randomized Incremental Construction (RIC) of search DAGs for pointlocation in planar subdivisions, nearest-neighbor search in 2D points, andextreme 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 expecteddepth 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) aconstruction time of ${\cal O}(n \log n)$. One application of these new andimproved results are \emph{remarkably simple} Las Vegas verifiers to obtainsearch DAGs with optimal worst-case bounds. This positively answers theconjectured logarithmic search cost in the DAG of Delaunay triangulations[Guibas et al.; ICALP 1990] and a conjecture on the depth of the DAG ofTrapezoidal subdivisions [Hemmer et al.; ESA 2012].

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