Halbieren einer Menge von Punkten in zwei optimale Teilmengen

Ich möchte eine Menge von Punkten in zwei gleich große Teilmengen aufteilen, damit die Summe der Quadrate innerhalb des Clusters minimiert wird. Wir können annehmen, dass sich die Punkte im zweidimensionalen euklidischen Raum befinden. Ich hoffe auf etwas schnelleres als einen allgemeinen k-Mittelwert-Clustering-Algorithmus, wenn k = d = 2 ist. Kann mich jemand in die Richtung eines guten Algorithmus dafür weisen?

Eine genaue Lösung ist nicht erforderlich, wenn wir eine gute Annäherung haben.

Vielen Dank!

Wenn Sie auf einer präzisen Partition bestehen, müssen Sie alle ausgeglichenen Partitionen einer Menge von Punkten in der Ebene durch eine Linie berechnen (die optimale Partition ist eine Voronoi-Partition, sodass die beiden Punktmengen durch eine Linie getrennt sind). Solche Partitionen sind als Sätze bekannt. Der schnellste Algorithmus zur Zeit für diese Arbeit in bekannten O ( n 4 / 3 log n ) für diese Partitionen im dualen Berechnung [dh die k -Niveau eines Satzes von n - Linien, für k = n /$k$$O(n^{4/3} \log n)$$k$$n$$k=n/2$]. Sobald Sie alle möglichen Partitionen haben, müssen Sie nur jede von ihnen überprüfen. Mit Standardtricks kann dies für jede Partition in konstanter Zeit durchgeführt werden.

$k$$k=n/2$

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

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