Membagi dua set poin menjadi dua himpunan bagian yang optimal

Saya ingin membagi satu set poin menjadi dua himpunan bagian yang berukuran sama sehingga jumlah kotak dalam-cluster diminimalkan. Kita dapat mengasumsikan bahwa titik-titik tersebut berada dalam ruang Euclidian dua dimensi. Saya berharap untuk sesuatu yang lebih cepat daripada algoritma klaster k-means umum mengingat bahwa k = d = 2. Adakah yang bisa mengarahkan saya ke arah algoritma yang baik untuk ini?

Solusi tepat tidak diperlukan jika kami memiliki perkiraan yang baik.

Terima kasih!

Jika Anda bersikeras pada partisi yang tepat, maka Anda perlu menghitung semua partisi seimbang dari satu set poin dalam pesawat dengan garis (partisi optimal adalah partisi Voronoi, sehingga dua set poin dipisahkan oleh garis). Partisi semacam itu dikenal sebagai set. Algoritma tercepat saat ini dikenal untuk pekerjaan ini di O ( n 4 / 3 log n ) untuk menghitung partisi ini di ganda [yaitu, k -tingkat dari satu set n baris, untuk k = n /$k$$O(n^{4/3} \log n)$$k$$n$$k=n/2$] Setelah Anda memiliki semua partisi yang mungkin, Anda hanya perlu memeriksa masing-masing partisi. Menggunakan trik standar, ini dapat dilakukan dalam waktu yang konstan untuk setiap partisi.

$k$$k=n/2$

$k$$O( \epsilon^{-2} \log n)$$n$

http://sarielhp.org/p/03/kcoreset/