# Timothy M. Chan's Publications: k-level algorithms

### Remarks on k-level algorithms in the plane

In light of recent developments, this paper re-examines the
fundamental geometric problem of how to construct the k-level in an
arrangement of n lines in the plane.
- The author's recent dynamic
data structure for planar convex hulls
improves a decade-old sweep-line algorithm by Edelsbrunner and Welzl,
which now runs in O(n log m + m log^{1+eps} n) deterministic time and
O(n) space, where m is the output size and eps is any positive
constant. We discuss simplification of the data structure in this
particular application, by viewing the problem kinetically.
- Har-Peled recently announced a randomized algorithm
with an expected running time of O((n+m) alpha(n) log n). We
observe that a version of an earlier randomized incremental algorithm
by Agarwal, de Berg, Matousek, and Schwarzkopf yields almost the
same result.
- The current combinatorial bound by Dey shows that m = O(nk^{1/3})
in the worst case. We give an algorithm that guarantees O(n log
n + nk^{1/3}) expected time.

### Random sampling, halfspace range reporting,
and construction of (<= k)-levels in three dimensions

Given n points in three dimensions, we show how to answer halfspace
range reporting queries in O(log n + k) expected time for an output
size k. Our data structure can be preprocessed in optimal O(n log
n) expected time. We apply this result to obtain the first optimal
randomized algorithm for the construction of the (<= k)-level in an
arrangement of n planes in three dimensions. The algorithm runs in
O(n log n + nk^2) expected time. Our techniques are based on random
sampling. Applications in two dimensions include an improved data
structure for "k nearest neighbors" queries, and an algorithm that
constructs the order-k Voronoi diagram in O(n log
n + nk log k) expected time.

**Copyright Notice**
The documents contained in this directory are included by the
contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a non-commercial basis. Copyright and
all rights therein are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked by each
author's copyright. These works may not be reposted without the
explicit permission of the copyright holder.

Timothy M. Chan
(Last updated 29 Mar 2014)