n個の識別可能なd次元点が与えられた場合、それらを線形に分離できるさまざまな方法の最大数はいくつですか？

Question

私たちが持っているとしましょう $n$ の識別可能なポイント $\mathbb{R}^d$。とは$f(n, d)$、単一の超平面を使用してそれらを分離できるさまざまな方法の最大数？飛行機の「左側」と「右側」を入れ替えることは違うとは思いません。

私は次の質問を見つけました$d = 2$ ケース、そう $f(n, 2) = \binom{n}{2} + 1$。

ポイントは、最も多くの分離が可能な位置にあると想定できます。にとって$d = 2$ これは（共線性がないことを超えて）問題ではないことが示されていますが、これがより高い次元（一般的な位置に点がある場合）にも当てはまるかどうかはわかりません。

Answer 1

と仮定して $n$点の一般的な位置、紙に示すように、「超平面によって誘導されるk次元にN個の点の集合の分割数」 EFハーディングによって、あなたが探している関数です。

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