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