The k-set problem

The k  -set problem is a classic open problem in Combinatorial Geometry, which is considered similar in spirit to incidence problems and to distance problems. While in recent years algebraic techniques led to significant progress in incidence and distance problems, so far none of the new methods were applied to the k  -set problem. This post briefly introduces the problem, and describes a way of reducing it to an incidence problem. I hope that it will get someone to think of the k  -set problem in an algebraic context and maybe come up with some new observations.

Let {\cal P}  be a set of n  points in {\mathbb R}^2  , and let 1\le k\le n/2  be an integer. A k  -set of {\cal P}  is a subset {\cal P}'\subset {\cal P}  of k  points such that there exists a line that separates {\cal P}'  from {\cal P}\setminus{\cal P}'  . That is, {\cal P}'  is on one open half-plane defined by the line, while {\cal P}\setminus{\cal P}'  is on the other half-plane. The following figure depicts two 5-sets of a set of 12 points.

5sets.eps

The k  -set problem asks for the maximum number of k  -sets that a set of n  -points in {\mathbb R}^2  can have. As a first silly example, note that the maximum number of 1-sets is exactly n  . It is not difficult to show that we may assume that no three points are collinear (specifically, perturbing the point set cannot significantly decrease the number of k  -sets).

The number of subsets of k  points of {\cal P}  is \Theta(n^k)  , so this is a straightforward upper bound for the maximum number of k  sets. However, we can easily obtain a significantly stronger upper bound. Consider a k  -set {\cal P}'\subset{\cal P}  that is separated by a line \ell  . We translate \ell  until it is incident to a point p\in {\cal P}'  and then rotate \ell  around p  until it is incident to a second point of {\cal P}  (not necessarily in {\cal P}'  ). For example, see the figure below. Thus, to find all of the k  -sets of {\cal P}  it suffices to consider every line that is incident to two points of {\cal P}  . Since there are O(n^2)  such lines, this is also an upper bound for the number of k  -sets.

kSetLineChange.eps

Continue reading

Advertisements