Was ist bei n unterscheidbaren d-dimensionalen Punkten die größte Anzahl verschiedener Arten, wie sie linear getrennt werden können?

Dec 01 2020

Angenommen, wir haben $n$ unterscheidbare Punkte in $\mathbb{R}^d$. Was ist$f(n, d)$, die größte Anzahl verschiedener Möglichkeiten, wie wir sie mit einer einzigen Hyperebene trennen können? Ich halte es nicht für unterschiedlich, die "linke" und "rechte" Seite des Flugzeugs zu tauschen.

Ich fand die folgende Frage für die$d = 2$ Fall, so $f(n, 2) = \binom{n}{2} + 1$.

Sie können davon ausgehen, dass sich die Punkte an einer Position befinden, die die meisten Trennungen zulässt. Zum$d = 2$ Es wird gezeigt, dass dies keine Rolle spielt (über keine Kollinearität hinaus), aber ich weiß nicht, ob dies auch für höhere Dimensionen gilt (mit Punkten in der allgemeinen Position).

Antworten

1 BillyJoe Dec 04 2020 at 22:29

Angenommen, die $n$Punkte in allgemeiner Position , wie in der Veröffentlichung "Die Anzahl der Partitionen einer Menge von N Punkten in k Dimensionen, die durch Hyperebenen induziert werden" von EF Harding gezeigt, ist die gesuchte Funktion:

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