k-sets

Let $n,k\in\mathbb{N}$ , let $P$ be a set of $n$ points, and let $S\subseteq P$ . The subset $S$ is a $k$ -set if $|S|=k$ and there is an open halfspace $H$ such that

S=P\cap H.

Determine the maximum possible number of $k$ -sets as a function of $n$ and $k$ . In particular, determine this maximum for point sets in two dimensions. Equivalently, determine 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