## Timothy M. Chan's Publications: The k-level and k-set problem

### On levels in arrangements of curves, III: further improvements

• 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)).