k-sets

What is the maximum number of $k$ -sets? (Equivalently, what is the maximum complexity of a $k$ -level in an arrangement of hyperplanes?)

Download

Abstract

Given a set of points, a $k$ -set is a subset of $k$ points obtained by intersecting the point set with an open halfspace. The open problem is to determine the maximum possible number of $k$ -sets. Even in two dimensions, the known upper and lower bounds remain separated.

Background and progress

The origin of the problem is uncertain. Let $n$ be the number of input points in the plane, and let $k$ be the cardinality of a $k$ -set. The maximum number of $k$ -sets is at most $O(nk^{1/3})$ [Dey, 1998], whereas the reported lower bound is only slightly superlinear [Toth, 2000]. In the halving case, where $n$ is even and $k=(n-2)/2$ , a later construction improved the constant in the exponent of the lower bound [Nivasch, 2008]. The gap remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p7.

Reference papers

Improved bounds on planar k-sets and related problemsT. K. DeyDiscrete Comput. Geom. · 1998
An improved, simple construction of many halving edgesGabriel NivaschProc. Snowbird Conference Discrete and Computational Geometry: Twenty Years Later · 2008
Point sets with many k-setsGéza TothProc. 16th Annu. ACM Sympos. Comput. Geom. · 2000

k-sets

Coming soon

Organizer