In discrete geometry, a k {\displaystyle k} -set of a finite point set S {\displaystyle S} in the Euclidean plane is a subset of k {\displaystyle k} elements of S {\displaystyle S} that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a k {\displaystyle k} -set of a finite point set is a subset of k {\displaystyle k} elements that can be separated from the remaining points by a hyperplane. In particular, when k = n / 2 {\displaystyle k=n/2} (where n {\displaystyle n} is the size of S {\displaystyle S} ), the line or hyperplane that separates a k {\displaystyle k} -set from the rest of S {\displaystyle S} is a halving line or halving plane.
The k {\displaystyle k} -sets of a set of points in the plane are related by projective duality to the k {\displaystyle k} -levels in an arrangement of lines. The k {\displaystyle k} -level in an arrangement of n {\displaystyle n} lines in the plane is the curve consisting of the points that lie on one of the lines and have exactly k {\displaystyle k} lines below them. Discrete and computational geometers have also studied levels in arrangements of more general kinds of curves and surfaces.[1]
It is of importance in the analysis of geometric algorithms to bound the number of k {\displaystyle k} -sets of a planar point set,[2] or equivalently the number of k {\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 O ( n k 1 / 3 ) {\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 Ω ( n c log k ) {\textstyle \Omega (nc^{\sqrt {\log k}})} for some constant c {\displaystyle c} , as shown by Tóth.[6]
In three dimensions, the best upper bound known is O ( n k 3 / 2 ) {\displaystyle O(nk^{3/2})} , and the best lower bound known is Ω ( n k c log k ) {\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 k {\displaystyle k} -sets is Θ ( ( n − k ) k ) {\displaystyle \Theta {\bigl (}(n-k)k{\bigr )}} , which follows from arguments used for bounding the complexity of k {\displaystyle k} th order Voronoi diagrams.[8]
For the case when k = n / 2 {\displaystyle k=n/2} (halving lines), the maximum number of combinatorially distinct lines through two points of S {\displaystyle S} that bisect the remaining points when k = 1 , 2 , … {\displaystyle k=1,2,\dots } is
Bounds have also been proven on the number of ≤ k {\displaystyle \leq k} -sets, where a ≤ k {\displaystyle \leq k} -set is a j {\displaystyle j} -set for some j ≤ k {\displaystyle j\leq k} . In two dimensions, the maximum number of ≤ k {\displaystyle \leq k} -sets is exactly n k {\displaystyle nk} ,[9] while in d {\displaystyle d} dimensions the bound is O ( n ⌊ d / 2 ⌋ k ⌈ d / 2 ⌉ ) {\displaystyle O(n^{\lfloor d/2\rfloor }k^{\lceil d/2\rceil })} .[10]
Edelsbrunner and Welzl[11] first studied the problem of constructing all k {\displaystyle k} -sets of an input point set, or dually of constructing the k {\displaystyle k} -level of an arrangement. The k {\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 k {\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 O ( n k 1 / 3 ) {\displaystyle O(nk^{1/3})} bound on the complexity of the k {\displaystyle k} -level.
Agarwal and Matoušek describe algorithms for efficiently constructing an approximate level; that is, a curve that passes between the ( k − δ ) {\displaystyle (k-\delta )} -level and the ( k + δ ) {\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 n / δ {\displaystyle n/\delta } and not on n {\displaystyle n} or k {\displaystyle k} .[13]
The planar k {\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 k {\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 O ( n k 1 / 3 ) {\displaystyle O(nk^{1/3})} bound on the complexity of the k {\displaystyle k} -level could be generalized to count the number of distinct optimal bases of any matroid with n {\displaystyle n} elements and rank k {\displaystyle k} .
For instance, the same O ( n k 1 / 3 ) {\displaystyle O(nk^{1/3})} upper bound holds for counting the number of different minimum spanning trees formed in a graph with n {\displaystyle n} edges and k {\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 Ω ( n log k ) {\displaystyle \Omega (n\log k)} , a weaker bound than that for the k {\displaystyle k} -set problem.[15] For more general matroids, Dey's O ( n k 1 / 3 ) {\displaystyle O(nk^{1/3})} upper bound has a matching lower bound.[16]