Clustering einer Menge von Punkten mit Kreisen

Question

Ich habe eine Gruppe von 100 Punkten in einer 2-D-Ebene mit bekannten x-y-Koordinaten. Ich möchte 25 Kreise so zeichnen, dass in jedem Kreis genau 4 Punkte vorhanden sind. Jeder Punkt muss in genau einem Kreis liegen. Können Sie den grundlegenden Algorithmus für die weitere Vorgehensweise angeben?

Hinweis: Ich habe einige Algorithmen untersucht, die k-Mittel beinhalten, aber keines hatte genau das, was ich möchte. Ich kenne python/go/matlab/c, wenn es bestimmte Module in dieser Sprache gibt, die nützlich sein könnten.

Answer 1

Ich denke, es gibt einige Konfigurationen, die keine Lösung hätten.

Alle in einem lokalen Maximum stecken Hill-Climbing-Algorithmus könnte.

Sie könnten alle Kombinationen von 4 Punktgruppen aufzählen und versuchen, Kreise um jede der Gruppen zu gruppieren, aber selbst dann können die engsten Kreise nicht zu einer Lösung führen, wenn ein Kreis mit einer besseren Anpassung möglich ist. Und die kombinatorische Explosion könnte diese Methode undurchführbar machen.