Étant donné n points de dimension d distinctifs, quel est le plus grand nombre de façons différentes de les séparer linéairement?
Supposons que nous ayons $n$ points distinctifs dans $\mathbb{R}^d$. Quel est$f(n, d)$, le plus grand nombre de façons différentes de les séparer en utilisant un seul hyperplan? Je ne considère pas que l'échange du côté «gauche» et «droit» de l'avion soit différent.
J'ai trouvé la question suivante pour le$d = 2$ cas, donc $f(n, 2) = \binom{n}{2} + 1$.
Vous pouvez supposer que les points sont dans une position permettant le plus grand nombre de séparations. Pour$d = 2$ il est montré que cela n'a pas d'importance (au-delà de l'absence de colinéarité), mais je ne sais pas si cela vaut également pour les dimensions supérieures (avec des points en position générale).
Réponses
En supposant que $n$points en position générale , comme indiqué dans l'article "Le nombre de partitions d'un ensemble de N points en k dimensions induites par les hyperplans" par EF Harding, la fonction que vous recherchez est:
$$f(n,d) = \sum_{k=0}^{d}{n-1 \choose k}$$