Diskussion:Dichtestes Punktpaar

Neuer Abschnitt /* Fehler im Programmcode */

Letzter Kommentar: vor 2 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Der Programmcode im Abschnitt "Programmierung" enthält zwei Fehler:

stripPoints wird mit new[] erstellt, es fehlt aber das korrespondierende delete[].
In getSmallestDistanceRecursive() fehlt ein return am Ende.

Außerdem implementiert dieser Programmcode nicht den O(n log n)-Algorithmus, der in "Divide-and-conquer-Algorithmus" beschrieben wird, sondern den einfacheren O(n log² n)-Algorithmus, der in jedem Aufruf von getSmallestDistanceOfStrip() die Punkte im "Streifen" nach ihrer Y-Koordinate sortiert. Er weist eine deutliche Ähnlichkeit zu dem C++-Code aus dem verlinkten Artikel Closest Pair of Points using Divide and Conquer algorithm auf.

--2001:A61:2466:E401:836A:E76B:2004:36AD 23:21, 27. Jan. 2022 (CET)Beantworten

Abschnitt hinzufügen