Учитывая n различимых d-мерных точек, каково наибольшее количество различных способов их линейного разделения?

Dec 01 2020

Предположим, у нас есть $n$ различимые точки в $\mathbb{R}^d$. Что такое$f(n, d)$, наибольшее количество различных способов, которыми мы можем разделить их с помощью одной гиперплоскости? Я не считаю, что поменять местами «левую» и «правую» стороны плоскости по-разному.

Я нашел следующий вопрос для$d = 2$ случай, так $f(n, 2) = \binom{n}{2} + 1$.

Вы можете предположить, что точки находятся в положении, допускающем наибольшее количество разделений. За$d = 2$ показано, что это не имеет значения (помимо коллинеарности), но я не знаю, верно ли это и для более высоких измерений (с точками в общем положении).

Ответы

1 BillyJoe Dec 04 2020 at 22:29

Если предположить $n$точки в общем положении , как показано в статье «Число разбиений набора из N точек в k измерениях, индуцированных гиперплоскостями» Э. Ф. Хардинга, функция, которую вы ищете:

$$f(n,d) = \sum_{k=0}^{d}{n-1 \choose k}$$