  We present the first optimal randomized algorithm for constructing the
order-$k$ Voronoi diagram of $n$ points in two dimensions. The expected running
time is $O(n\log n + nk)$, which improves the previous, two-decades-old result
of 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 combination
with Ramos's cutting construction, to reduce the problem to verifying an
order-$k$ Voronoi diagram, and (ii) solve the verification problem by a new
divide-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 constructing
the $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 best
upper bounds on the combinatorial complexity of the $k$-level. Previously, the
same time bound in two dimensions was obtained by Chan (1999) but with
randomization.
