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.
Combinatorial bounds It is of importance in the analysis of geometric algorithms to bound the number of k {\displaystyle k} -sets of a planar point set, or equivalently the number of k {\displaystyle k} -levels of a planar line arrangement, a problem first studied by Lovász and Erdős et al. 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 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. 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}})} . 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. 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} , 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 })} .
Halving lines
… excerpt ends here. Continue reading the full article.
