K-set (geometry)

that can be strictly separated from the remaining points by a line.

More generally, in Euclidean space of higher dimensions, a

-set of a finite point set is a subset of

elements that can be separated from the remaining points by a hyperplane.

-sets of a set of points in the plane are related by projective duality to the

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

-sets of a planar point set,[2] or equivalently the number of

-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

, as was shown by Tamal Dey[5] using the crossing number inequality of Ajtai, Chvátal, Newborn, and Szemerédi.

[7] For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of

(halving lines), the maximum number of combinatorially distinct lines through two points of

In two dimensions, the maximum number of

[10] Edelsbrunner and Welzl[11] first studied the problem of constructing all

-sets of an input point set, or dually of constructing the

-level version of their algorithm can be viewed as a plane sweep algorithm that constructs the level in left-to-right order.

-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

Agarwal and Matoušek describe algorithms for efficiently constructing an approximate level; that is, a curve that passes between the

They show that such an approximation can be found, consisting of a number of line segments that depends only on

-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

, and must find the minimum weight basis of the matroid for each possible value of

If one graphs the weight functions as lines in a plane, the

-level of the arrangement of these lines graphs as a function of

the weight of the largest element in an optimal basis in a uniform matroid, and Dey showed that his

-level could be generalized to count the number of distinct optimal bases of any matroid with

upper bound holds for counting the number of different minimum spanning trees formed in a graph with

vertices, when the edges have weights that vary linearly with a parameter

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