# Maximum number of ways of splitting a set of points with an hyperplane

Given a set $$S$$ of $$n$$ points in $$\mathbb{R}^d$$, let $$D_S$$ be the set $$\{\mathbf{v}=|\mathbf{u}-\mathbf{u'}|: \mathbf{u},\mathbf{u'}\in S\}$$ (where $$\forall i=1,2,\ldots, d$$, $$\mathbf{v}_i=|\mathbf{u}_i-\mathbf{u'}_i|$$). Thus, we have $$|D_S|\le{{n}\choose{2}}$$.

Given any vector $$\mathbf{w}\in\mathbb{R}^d$$ such that $$\mathbf{w}_i>0$$ $$\forall i=1,2,\ldots, d$$ (i.e. belonging to the positive orthant of $$\mathbb{R}^d$$), consider now the binary "labelling" function $$f_\mathbf{w}:D_S\to\{0,1\}$$ defined as $$f_{\mathbf{w}}(\mathbf{v})=\mathbb{1}_{\mathbf{w}^{\top}\mathbf{v}\ge 0}$$ (i.e. for all $$\mathbf{v}\in D_S$$, if $$\mathbf{w}^{\top}\mathbf{v}\ge 0$$ then $$f_{\mathbf{w}}(\mathbf{v})=1$$, otherwise $$f_{\mathbf{w}}(\mathbf{v})=0$$).

Question: What is the maximum number (expressed as a function of $$n$$ and $$d$$), over all possible sets $$S\in\mathbb{R}^d$$, of distinct binary labellings of the points of $$D_S$$ that one can obtain through $$f_{\mathbf{w}}$$ varying $$\mathbf{w}$$ within the positive orthant of $$\mathbb{R}^d$$?

• If I've understood your question correctly, the maximum is at least $n^{d-1} e^{\Omega(\sqrt{\log n})}$, because there are at least that many halving hyperplanes. This is a result of Géza Tóth. – Joseph O'Rourke Jul 20 '19 at 14:01
• I am also interested in finding a (possibly tight) upper bound. – Penelope Benenati Jul 20 '19 at 14:30
• I am referring to: Tóth, Géza. "Point sets with many $k$-sets." Discrete & Computational Geometry 26, no. 2 (2001): 187-194. Journal link. – Joseph O'Rourke Jul 20 '19 at 14:33
• Is it easy to answer for $d=2$? – Gerry Myerson Jul 20 '19 at 23:27
• @Gerry No, it is also open, the best bound is $O(n^{4/3})$ due to Dey. See this link: jeffe.cs.illinois.edu/open/ksets.html – domotorp Jul 21 '19 at 1:26