wie wärs mit folgendem:

du kannst die gesamtgröße des gebietes bestimmen (max min der koordinaten, lineare laufzeit)
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)
wenn du nun zwei beliebige punkte betrachtest, dann kannst du ihren abstand mit diesem mittleren gruppenabstand vergleichen und so raten, ob die zwei punkte zu einer gruppe (abstand viel kleiner als gruppenabstand) oder zu verschiedenen gruppen (abstand in größenordnung des gruppenabstandes) gehören.
wenn du auf diese weise eine einteilung gefunden hast, kannst du diese noch mal verifizieren und gegebenfalls koorigieren.

so macht das vielleicht auch unser hirn: schauen wie groß das ganze ist und daraus schätzen was man als nah und was als weit entfernt betrachtet. dann lokal prüfen (innerhalb einer gefundenen gruppe), obs passt.

wenn man erst einmal eine gruppe identifiziert hat (abstand innerhalb der gruppe klein, zu allen anderen punkten groß) dann kann man sie im weiteren ausklammern und hat das problem reduziert. 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.

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.