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

Given a planar map of $n$ segments in which we wish to efficiently locatepoints, we present the first randomized incremental construction of thewell-known trapezoidal-map search-structure that only requires expected $O(n\log n)$ preprocessing time while deterministically guaranteeing worst-caselinear storage space and worst-case logarithmic query time. This settles a longstanding open problem; the best previously known construction time of such astructure, which is based on a directed acyclic graph, so-called the historyDAG, and with the above worst-case space and query-time guarantees, wasexpected $O(n \log^2 n)$. The result is based on a deeper understanding of thestructure of the history DAG, its depth in relation to the length of itslongest search path, as well as its correspondence to the trapezoidal searchtree. Our results immediately extend to planar maps induced by finitecollections of pairwise interior disjoint well-behaved curves.

Optimal randomized incremental construction for guaranteed logarithmic planar point location