Punktpaar mit minimaler Distanz

[Wieninger]

Hallo,

ich habe von einem deterministischen Algorithmus zur Bestimmung des Punktepaares mit minimaler Distanz in der euklidischen Ebene gehört, welcher eine Laufzeit von nur O(n) statt O(n log(n)) haben soll.

Ist jemandem aus diesem Forum etwas über diesen Algorithmus bekannt?
Gibt es vlt einen Link zu dem entsprechenden Paper?

Ich finde per Google leider nur die üblichen n log(n)-komplexen oder randomisierte Verfahren.

[wiki_]

Was ist an http://en.wikipedia.org/wiki/Closest_pair_of_points_problem nicht klar?

[Wieninger]

Finde den Algorithmus nicht.
Bitte genauer angeben.

[Jester]

Da steht, dass n log n optimal ist. Allerdings hängt das natürlich vom rechenmodell ab.