K-set (geometry)

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.