Ein möglicher Ansatz
wäre, jeden Punkt der Menge mit allen andern Punkten zu vergleichen, um so die geringste Distanz ausfindig zu machen. Doch dieser Weg ist nicht sehr effizient und kommt daher nicht in Frage.
Iterativ
umgesetzt sieht die Idee so aus, dass man die Menge an Punkten zunächst einmal nach ihren x-Koordinaten aufsteigend sortiert. Anschließend wird der 1. Punkt mit dem 2. verglichen und die Distanz der beiden Punkte als Ausgangswert hergenommen und im Weiteren nun mit MinSoFar bezeichnet.
Nun überprüft man nach und nach alle weiteren Punkte in der Reihenfolge ihrer x-Koordinaten,
also Punkt 2 bis Punkt n.
An jedem neuen Punkt X wird nun jeweils MinSoFar Schritte nach links, sowie nach oben und unten, geschaut,
ob ein Punkt Y in diesem "Rechteck" liegt.
Falls dies der Fall ist, wird die Distanz der von jedem der im Rechteck enthaltenen Punkte zum Punkt X überprüft,
und falls diese kleiner als das bisherige MinSoFar ist, wird dieses neu gesetzt.
Theoretisch würde es genügen, alle in dem um den aktuellen Punkt aufgespannten Halbkreis mit Radius MinSoFar liegenden Punkte zu überprüfen. Da dies jedoch technisch schwer umsetzbar ist, nimmt man ein paar Vergleiche mehr in Kauf und sucht in dem aufgespannten Rechteck. Die Laufzeit ist im Allgemeinen nahezu identisch, da die zu überprüfende Fläche, und damit die Anzahl der zu überprüfenden Punkte, nicht sehr ansteigt.