Diberikan n titik-titik berdimensi-d yang dapat dibedakan, berapakah jumlah terbesar dari cara-cara berbeda yang dapat dipisahkan secara linier?

Question

Misalkan kita punya $n$ poin yang dapat dibedakan di $\mathbb{R}^d$. apa yang$f(n, d)$, jumlah terbesar dari cara berbeda untuk memisahkannya menggunakan hyperplane tunggal? Saya tidak menganggap menukar sisi 'kiri' dan 'kanan' pesawat menjadi berbeda.

Saya menemukan pertanyaan berikut untuk$d = 2$ kasus, jadi $f(n, 2) = \binom{n}{2} + 1$.

Anda dapat berasumsi bahwa titik-titik berada dalam posisi yang memungkinkan jumlah pemisahan paling banyak. Untuk$d = 2$ ditunjukkan bahwa ini tidak masalah (di luar collinearity), tetapi saya tidak tahu apakah ini juga berlaku untuk dimensi yang lebih tinggi (dengan titik dalam posisi umum).

Answer 1

Dengan asumsi $n$titik dalam posisi umum , seperti yang ditunjukkan di kertas "Jumlah partisi dari sekumpulan titik N dalam dimensi k yang diinduksi oleh hyperplanes" oleh EF Harding, fungsi yang Anda cari adalah:

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