Points separated from others by a line
In discrete geometry, a formula_1-set of a finite point set formula_2 in the Euclidean plane is a subset of formula_1 elements of formula_2 that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a formula_1-set of a finite point set is a subset of formula_1 elements that can be separated from the remaining points by a hyperplane. In particular, when formula_7 (where formula_8 is the size of formula_2), the line or hyperplane that separates a formula_1-set from the rest of formula_2 is a halving line or halving plane.
The formula_1-sets of a set of points in the plane are related by projective duality to the formula_1-levels in an arrangement of lines. The formula_1-level in an arrangement of formula_8 lines in the plane is the curve consisting of the points that lie on one of the lines and have exactly formula_1 lines below them. Discrete and computational geometers have also studied levels in arrangements of more general kinds of curves and surfaces.
Combinatorial bounds.
 ;templatestyles src="Unsolved/styles.css" / ;
Unsolved problem in mathematics:
What is the largest possible number of halving lines for a set of formula_8 points in the plane?
It is of importance in the analysis of geometric algorithms to bound the number of formula_1-sets of a planar point set, or equivalently the number of formula_1-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 formula_20, 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 formula_21 for some constant formula_22, as shown by Tóth.
In three dimensions, the best upper bound known is formula_23, and the best lower bound known is formula_24.
For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of formula_1-sets is 
formula_26, which follows from arguments used for bounding the complexity of formula_1th order Voronoi diagrams.
For the case when formula_7 (halving lines), the maximum number of combinatorially distinct lines through two points of formula_2 that bisect the remaining points when formula_30 is
 ;templatestyles src="Block indent/styles.css"/ ;
Bounds have also been proven on the number of formula_31-sets, where a formula_31-set is a formula_33-set for some formula_34. In two dimensions, the maximum number of formula_31-sets is exactly formula_36, while in formula_37 dimensions the bound is formula_38.
Construction algorithms.
Edelsbrunner and Welzl first studied the problem of constructing all formula_1-sets of an input point set, or dually of constructing the formula_1-level of an arrangement. The formula_1-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 formula_1-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 surveys subsequent results on this problem, and shows that it can be solved in time proportional to Dey's formula_20 bound on the complexity of the formula_1-level.
Agarwal and Matoušek describe algorithms for efficiently constructing an approximate level; that is, a curve that passes between the formula_45-level and the formula_46-level for some small approximation parameter formula_47. They show that such an approximation can be found, consisting of a number of line segments that depends only on formula_48 and not on formula_8 or formula_1.
Matroid generalizations.
The planar formula_1-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 formula_52, and must find the minimum weight basis of the matroid for each possible value of formula_52. If one graphs the weight functions as lines in a plane, the formula_1-level of the arrangement of these lines graphs as a function of formula_52 the weight of the largest element in an optimal basis in a uniform matroid, and Dey showed that his formula_20 bound on the complexity of the formula_1-level could be generalized to count the number of distinct optimal bases of any matroid with formula_8 elements and rank formula_1.
For instance, the same formula_20 upper bound holds for counting the number of different minimum spanning trees formed in a graph with formula_8 edges and formula_1 vertices, when the edges have weights that vary linearly with a parameter formula_52. This parametric minimum spanning tree problem has been studied by various authors and can be used to solve other bicriterion spanning tree optimization problems.
However, the best known lower bound for the parametric minimum spanning tree problem is formula_64, a weaker bound than that for the formula_1-set problem. For more general matroids, Dey's formula_20 upper bound has a matching lower bound.
Notes.
 ;templatestyles src="Reflist/styles.css" / ;
References.
 ;templatestyles src="Refbegin/styles.css" / ;