Dados n pontos d-dimensionais distinguíveis, qual é o maior número de maneiras diferentes pelas quais eles podem ser separados linearmente?

Question

Suponha que temos $n$ pontos distinguíveis em $\mathbb{R}^d$. O que é$f(n, d)$, o maior número de maneiras diferentes de separá-los usando um único hiperplano? Não considero que trocar o lado 'esquerdo' e 'direito' do avião seja diferente.

Eu encontrei a seguinte pergunta para o$d = 2$ caso, então $f(n, 2) = \binom{n}{2} + 1$.

Você pode assumir que os pontos estão em uma posição que permite o maior número de separações. Para$d = 2$ é mostrado que isso não importa (além de nenhuma colinearidade), mas não sei se isso também se aplica a dimensões superiores (com pontos na posição geral).

Answer 1

Assumindo o $n$pontos em posição geral , como mostrado no artigo "O número de partições de um conjunto de N pontos em k dimensões induzidas por hiperplanos" por EF Harding, a função que você está procurando é:

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