K-set (geometry)

It is of importance in the analysis of geometric algorithms to bound the number of ${\displaystyle k}$-sets of a planar point set,[2] or equivalently the number of ${\displaystyle k}$-levels of a planar line arrangement, a problem first studied by Lovász[3] and Erdős et al.[4] The best known upper bound for this problem is ${\displaystyle O(nk^{1/3})}$, as was shown by Tamal Dey[5] using the crossing number inequality of Ajtai, Chvátal, Newborn, and Szemerédi. However, the best known lower bound is far from Dey's upper bound: it is ${\textstyle \Omega (nc^{\sqrt {\log k}})}$ for some constant ${\displaystyle c}$, as shown by Tóth.[6]

In three dimensions, the best upper bound known is ${\displaystyle O(nk^{3/2})}$, and the best lower bound known is ${\textstyle \Omega (nkc^{\sqrt {\log k}})}$.[7] For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of ${\displaystyle k}$-sets is ${\displaystyle \Theta {\bigl (}(n-k)k{\bigr )}}$, which follows from arguments used for bounding the complexity of ${\displaystyle k}$th order Voronoi diagrams.[8]

For the case when ${\displaystyle k=n/2}$ (halving lines), the maximum number of combinatorially distinct lines through two points of ${\displaystyle S}$ that bisect the remaining points when ${\displaystyle k=1,2,\dots }$ is

Bounds have also been proven on the number of ${\displaystyle \leq k}$-sets, where a ${\displaystyle \leq k}$-set is a ${\displaystyle j}$-set for some ${\displaystyle j\leq k}$. In two dimensions, the maximum number of ${\displaystyle \leq k}$-sets is exactly ${\displaystyle nk}$,[9] while in ${\displaystyle d}$ dimensions the bound is ${\displaystyle O(n^{\lfloor d/2\rfloor }k^{\lceil d/2\rceil })}$.[10]

Edelsbrunner and Welzl[11] first studied the problem of constructing all ${\displaystyle k}$-sets of an input point set, or dually of constructing the ${\displaystyle k}$-level of an arrangement. The ${\displaystyle k}$-level version of their algorithm can be viewed as a plane sweep algorithm that constructs the level in left-to-right order. Viewed in terms of ${\displaystyle k}$-sets of point sets, their algorithm maintains a dynamic convex hull for the points on each side of a separating line, repeatedly finds a bitangent of these two hulls, and moves each of the two points of tangency to the opposite hull. Chan[12] surveys subsequent results on this problem, and shows that it can be solved in time proportional to Dey's ${\displaystyle O(nk^{1/3})}$ bound on the complexity of the ${\displaystyle k}$-level.

Agarwal and Matoušek describe algorithms for efficiently constructing an approximate level; that is, a curve that passes between the ${\displaystyle (k-\delta )}$-level and the ${\displaystyle (k+\delta )}$-level for some small approximation parameter ${\displaystyle \delta }$. They show that such an approximation can be found, consisting of a number of line segments that depends only on ${\displaystyle n/\delta }$ and not on ${\displaystyle n}$ or ${\displaystyle k}$.[13]

The planar ${\displaystyle k}$-level problem can be generalized to one of parametric optimization in a matroid: one is given a matroid in which each element is weighted by a linear function of a parameter ${\displaystyle \lambda }$, and must find the minimum weight basis of the matroid for each possible value of ${\displaystyle \lambda }$. If one graphs the weight functions as lines in a plane, the ${\displaystyle k}$-level of the arrangement of these lines graphs as a function of ${\displaystyle \lambda }$ the weight of the largest element in an optimal basis in a uniform matroid, and Dey showed that his ${\displaystyle O(nk^{1/3})}$ bound on the complexity of the ${\displaystyle k}$-level could be generalized to count the number of distinct optimal bases of any matroid with ${\displaystyle n}$ elements and rank ${\displaystyle k}$.

For instance, the same ${\displaystyle O(nk^{1/3})}$ upper bound holds for counting the number of different minimum spanning trees formed in a graph with ${\displaystyle n}$ edges and ${\displaystyle k}$ vertices, when the edges have weights that vary linearly with a parameter ${\displaystyle \lambda }$. This parametric minimum spanning tree problem has been studied by various authors and can be used to solve other bicriterion spanning tree optimization problems.[14]

However, the best known lower bound for the parametric minimum spanning tree problem is ${\displaystyle \Omega (n\log k)}$, a weaker bound than that for the ${\displaystyle k}$-set problem.[15] For more general matroids, Dey's ${\displaystyle O(nk^{1/3})}$ upper bound has a matching lower bound.[16]

• Halving lines and k-sets, Jeff Erickson
• The Open Problems Project, Problem 7: k-sets