ich hab noch was gefunden:
ein minimal spannender baum hat als knoten die punkte und verbindet sie durch kanten, so dass die gesamtlänge der kanten minimal ist. daraus ergibt sich, das es zwischen zwei gruppen nur eine kante geben wird und die punkte einer gruppe im baum eng benachbart sein müssen. damit könnte man die gruppen also finden.
die berechnung erfordert NlogN zeit.

das finden der zwei dichtest benachbarten punkte kostet ebenfalls NlogN zeit.

die lösung deines problems sollte wohl etwas zwischen N^2 und NlogN zeit benötigen.

wieviele punkte hast du denn?