@Felix
Dein Problem mit k_min und max kann ich nicht nachvollziehen.
Naja, bei den bisherigen Varianten sehe ich halt ein Problem darin, daß eventuell die Anzahl der Punkte pro Gruppe nicht korrekt ist. Etwa wenn zwei Gruppen nah beieinander (oder gar an der selben Stelle, auch das ist denkbar) liegen, oder wenn ein Punkt genau zwischen zwei Gruppen liegt etc.

Aber vielleicht habe ich ja auch irgendwo einen Denkfehler, und solche Situationen würden bei den angesprochenen Verfahren kein Problem darstellen.


du kannst die gesamtgröße des gebietes bestimmen
Ok, soweit kein Problem, ich normiere die Daten einfach auf einen Bereich von 0...1.

du kennst die anzahl der gruppen, daher kannst du den wahrscheinlich durchschnittlichen abstand der gruppen abschätzen (bei nem quadratischen gebiet und 4 gruppen zb. etwa halbe kantenlänge)
hmm, aber es kann ja durchaus vorkommen, daß zwei Gruppen extrem nah benachbart sind, die anderen hingegen weit voneinander entfernt

wenn du auf diese weise eine einteilung gefunden hast, kannst du diese noch mal verifizieren und gegebenfalls koorigieren.
nur wie soll ich diese Einteilung verifizieren? Wie kann ich herausfinden ob ich einen Punkt falsch zugeordnet habe?

am ende bleibt dann womöglich ein rest der ne spezialsituation darstellt (z.b. zwei eng benachbarte gruppen) für die man eine andere strategie einsetzt.
Wobei du voraussetzt, daß man überhaupt erstmal erkennt daß es zwei oder mehrere eng benachbarte Gruppen gibt, denn sonst könnte man für diese ja dann keine andere Strategie einsetzen.


deshalb wäre es vielleicht hilfreich mal ein paar fallbeispiele (typische punktmengen) festzulegen. zum einen, um etwas handfestes zu haben, über das man reden kann. und zum anderen um testdaten zu haben, um die algorithmen im geiste und später als programm zu testen.
Naja, setz 9 Punkte in 3 2er und einer 3er Gruppe an beliebige Stellen in einen Würfel mit einer Kantenlänge von 1.

Es gibt da eigentlich keine wirklich "typischen" Szenarios, denn die Gruppen können so ziemlich überall innerhalb des Wertebereichs (=des Würfels) liegen. (theoretisch wäre es sogar denkbar - wenn auch recht unwahrscheinlich - daß alle 9 Punkte an der gleichen Position liegen)


Um konkrete Testdaten zu haben würde ich also dazu tendieren einige worst-case Szenarien zu definieren...
z.B. zwei Gruppen die so eng beieinander liegen, daß sie nicht mehr unterscheidbar sind, oder eine 3er Gruppe bei der ein zugehöriger Punkt auf halbem Weg zu einer benachbarten 2er Gruppe liegt, oder irgendwie sowas.