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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present the first optimal randomized algorithm for constructing theorder-$k$ Voronoi diagram of $n$ points in two dimensions. The expected runningtime is $O(n\log n + nk)$, which improves the previous, two-decades-old resultof Ramos (SoCG'99) by a $2^{O(\log^*k)}$ factor. To obtain our result, we (i)use a recent decision-tree technique of Chan and Zheng (SODA'22) in combinationwith Ramos's cutting construction, to reduce the problem to verifying anorder-$k$ Voronoi diagram, and (ii) solve the verification problem by a newdivide-and-conquer algorithm using planar-graph separators.  We also describe a deterministic algorithm for constructing the $k$-level of$n$ lines in two dimensions in $O(n\log n + nk^{1/3})$ time, and constructingthe $k$-level of $n$ planes in three dimensions in $O(n\log n + nk^{3/2})$time. These time bounds (ignoring the $n\log n$ term) match the current bestupper bounds on the combinatorial complexity of the $k$-level. Previously, thesame time bound in two dimensions was obtained by Chan (1999) but withrandomization.

An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism