A set of six points (red), its six 2-sets (the sets of points contained in the blue ovals), and lines separating each ${\displaystyle k}$-set from the remaining points (dashed black).

In discrete geometry, a ${\displaystyle k}$-set of a finite point set ${\displaystyle S}$ in the Euclidean plane is a subset of ${\displaystyle k}$ elements of ${\displaystyle S}$ that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a ${\displaystyle k}$-set of a finite point set is a subset of ${\displaystyle k}$ elements that can be separated from the remaining points by a hyperplane. In particular, when ${\displaystyle k=n/2}$ (where ${\displaystyle n}$ is the size of ${\displaystyle S}$), the line or hyperplane that separates a ${\displaystyle k}$-set from the rest of ${\displaystyle S}$ is a halving line or halving plane.

The ${\displaystyle k}$-sets of a set of points in the plane are related by projective duality to the ${\displaystyle k}$-levels in an arrangement of lines. The ${\displaystyle k}$-level in an arrangement of ${\displaystyle n}$ lines in the plane is the curve consisting of the points that lie on one of the lines and have exactly ${\displaystyle k}$ lines below them. Discrete and computational geometers have also studied levels in arrangements of more general kinds of curves and surfaces.^[1]

Combinatorial bounds

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]

Construction algorithms

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]

Matroid generalizations

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]

Notes

References

External links

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