Timothy M. Chan's Publications: The k-level and k-set problem
On levels in arrangements of curves, III: further improvements
We revisit the problem of bounding the combinatorial complexity of
the k-level in a two-dimensional arrangement of n curves.
We give a number of small improvements over the results from the
author's previous paper (FOCS'03).
For example:
- For pseudo-parabolas, we obtain an upper bound of
O(n^{3/2} log n), which improves the previous bound of
O(n^{3/2} log^2 n).
- For 3-intersecting curves, we obtain an upper bound of
O(n^{2-1/(3+sqrt{7})}) = O(n^{1.823}), the first improvement
over the previous bound of O(n^{11/6}) = O(n^{1.834}).
- For s-intersecting curves or curve segments with s>= 3,
we obtain an upper bound of
O(n^{2 - 1/2s - delta_s}) if s is
odd, and O(n^{2 - 1/(2(s-1)) - delta_s}) if s is even,
for some constant delta_s > 0.
- For pseudo-segments, we obtain an upper bound of
O(n^{4/3} log^{1/3-delta} n) for some constant delta > 0;
the previous bound was O(n^{4/3} log^{2/3} n).
- For s-intersecting curve segments
such that all but B pairs intersect at most once, we
obtain an upper bound of
O((n^{4/3} + n^{1+delta}B^{1/3-delta})log^{1/3-delta} n + B)
for some constant delta > 0.
We also observe that better concrete bounds for k-levels for
constant values of n could in principle lead to better asymptotic
bounds for arbitrary n.
On the bichromatic k-set problem
We study a bichromatic version of the well-known k-set
problem: given two sets R and B of points of total size n and an
integer k, how many subsets of the form
(R\cap h) \cup (B - h) can have size exactly k over all
halfspaces h? In the dual, the problem is asymptotically equivalent
to determining the worst-case combinatorial
complexity of the k-level in an arrangement
of n halfspaces.
Disproving a conjecture by Linhart (1993), we present the first nontrivial
upper bound for all k << n in two dimensions: O(nk^{1/3} +
n^{5/6-e}k^{2/3+2e} + k^2) for any fixed e > 0. In three
dimensions, we obtain the bound O(nk^{3/2} + n^{0.5034}k^{2.4932} +
k^3). Incidentally, this also implies a new upper bound for the
original k-set problem in four dimensions: O(n^2k^{3/2} +
n^{1.5034}k^{2.4932} + nk^3), which improves the best previous result
for all k << n^{0.923}. Extensions to other cases, such as
arrangements of disks, are also discussed.
On levels in arrangements of surfaces in three dimensions
A favorite open problem in combinatorial geometry is to determine the
worst-case complexity of a level in an arrangement. Up to
now, nontrivial upper bounds in three dimensions are known only for
the linear cases of planes and triangles. We propose the first
technique that can deal with more general surfaces in three
dimensions. For example, in an arrangement of n "pseudo-planes"
or "pseudo-spheres" (where each triple of surfaces has at most two
common intersections), we prove that there are at most O(n^{2.997})
vertices of any given level.
On levels in arrangements of curves, II: a simple
inequality and its consequence
We give a surprisingly short proof that in any planar arrangement of
n curves where each pair intersects at most a fixed number (s) of
times, the k-level has subquadratic (O(n^{2-1/2s}))
complexity. This answers one of the main open problems from the
author's previous paper (FOCS'00),
which provided a weaker bound for a
restricted class of curves only (graphs of degree-s polynomials).
When combined with existing tools (cutting curves, sampling, etc.),
the new idea generates a slew of improved k-level results for
most of the curve families studied earlier, including a
near-O(n^{3/2}) bound for parabolas.
On levels in arrangements of curves
Analyzing the worst-case complexity of the k-level in a planar
arrangement of n curves is a fundamental problem in combinatorial
geometry. We give the first subquadratic upper bound (roughly
O(nk^{1-1/(9*2^{s-3})}) for curves that are graphs of polynomial
functions of an arbitrary fixed degree s. Previously, nontrivial
results were known only for the case s=1 and s=2. We also improve the
earlier bound for pseudo-parabolas (curves that pairwise intersect at
most twice) to O(nk^{7/9} log^{2/3} k). The proofs are simple and
rely on a theorem of Tamaki and Tokuyama on cutting pseudo-parabolas
into pseudo-segments, as well as a new observation for cutting
pseudo-segments into pieces that can be extended to pseudo-lines. We
mention applications to parametric and kinetic minimum spanning trees.
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.
On levels in arrangements of lines, segments, planes, and triangles
(with
Pankaj K. Agarwal,
Boris Aronov, and
Micha Sharir)
We consider the problem of bounding the complexity of the k-th
level in an arrangement of n curves or surfaces, a problem dual to,
and an extension of, the well-known k-set problem.
Among other results, we prove a new bound, O(n k^{5/3}), on
the complexity of the k-th level in an arrangement of n planes in
R^3, or on the number of k-sets in a set of n points
in three dimensions, and we
show that the complexity of the k-th level in an arrangement
of n line segments in the plane is O(n sqrt(k) alpha(n/k)), and that the
complexity of the k-th level in an arrangement of n triangles
in 3-space is O(n^2 k^{5/6} alpha(n/k)).
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 Chan
(Last updated Nov 2020)