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$?

  • 2
    $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Jul 20 '19 at 14:01
  • $\begingroup$ I am also interested in finding a (possibly tight) upper bound. $\endgroup$ – Penelope Benenati Jul 20 '19 at 14:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Jul 20 '19 at 14:33
  • 1
    $\begingroup$ Is it easy to answer for $d=2$? $\endgroup$ – Gerry Myerson Jul 20 '19 at 23:27
  • 2
    $\begingroup$ @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 $\endgroup$ – domotorp Jul 21 '19 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.