K-set (geometry)

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

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

K-sets are related by projective duality to k-levels in line arrangements; the k-level in an arrangement of n lines in the plane is the curve consisting of the points that lie on one of the lines and have exactly 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 k-sets of a planar point set,^[2] or equivalently the number of 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 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 Ω(n exp(c (logk)^1/2)) for some constant c, as shown by Tóth.^[6]

In three dimensions, the best upper bound known is O(nk^3/2), and the best lower bound known is Ω(nk exp(c (logk)^1/2)).^[7] For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of k-sets is Θ((n-k)k), which follows from arguments used for bounding the complexity of k-th order Voronoi diagrams.^[8]

For the case when k = n/2 (halving lines), the maximum number of combinatorially distinct lines through two points of S that bisect the remaining points when k = 1, 2, ... is

1,3,6,9,13,18,22... (sequence A076523 in the OEIS).

Bounds have also been proven on the number of ≤k-sets, where a ≤k-set is a j-set for some j ≤ k. In two dimensions, the maximum number of ≤k-sets is exactly nk,^[9] while in 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 k-sets of an input point set, or dually of constructing the k-level of an arrangement. The 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 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 O(nk^1/3) bound on the complexity of the k-level.

Agarwal and Matoušek describe algorithms for efficiently constructing an approximate level; that is, a curve that passes between the (k - d)-level and the (k + d)-level for some small approximation parameter d. They show that such an approximation can be found, consisting of a number of line segments that depends only on n/d and not on n or k.^[13]

Matroid generalizations[]

The planar 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 λ, 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 k-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 O(nk^1/3) bound on the complexity of the k-level could be generalized to count the number of distinct optimal bases of any matroid with n elements and rank k.

For instance, the same O(nk^1/3) upper bound holds for counting the number of different minimum spanning trees formed in a graph with n edges and k 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 Ω(n α(k)), where α is the inverse Ackermann function, an even weaker bound than that for the k-set problem. For more general matroids, Dey's O(nk^1/3) upper bound has a matching lower bound.^[15]

Notes[]

References[]

External links[]

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