Let $S$ be a set of $2n$ points in $\mathbb{R}^2$. Which is the maximum number of different bi-partitions of $S$ generated by a straight line?


More precisely, which is the maximum number of partitions $S=S\_1 \sqcup S\_2$ such that $|S\_1|=n$ and there exists a line $\ell$ such that $S\_1$ and $S\_2$ and are the intersection of $S$ with the two open half-planes determined by $\ell$.



Bi-partitioning $2n$ points on the plane with a straight line
These are called halving lines, and we don't know the exact order of their magnitude, just that it is between $\Omega(n2^{\sqrt\log n})$ and $O(n^{4/3})$.
For more information, see <https://jeffe.cs.illinois.edu/open/ksets.html>.


