Coding Challenge: Gift-Wrapping-Algorithmus

Nach einer mehrwöchigen Pause meldet sich Daniel Shiffman mit einer neuen Coding Challenge zurück. Er programmiert darin den Gift-Wrapping-Algorithmus zur Berechnung der konvexen Hülle einer Punktmenge. Dieser Algorithmus – nach seinem Erfinder R. A. Jarvis, der ihn 1973 veröffentlichte, auch Jarvis-March genannt – ist nicht gerade sonderlich effizient, er besitzt eine Laufzeit von $Θ(nh)$, wobei $n$ die Anzahl aller Punkte und $h$ die Zahl der Punkte auf der konvexen Hülle ist. Im Extremfall, wenn alle Punkte auf der konvexen Hülle liegen, beträgt die Laufzeit $Θ(n^2)$.

Der Algorithmus gehört zum Gebiet der Algorithmischen Geometrie, dem Teilgebiet der Informatik, das sich mit der algorithmischen Lösung geometrisch formulierter Probleme beschäftigt. Shiffman hat ihn in P5.js, dem JavaScript-Mode von Processing programmiert und versprochen, in nächster Zukunft noch ein paar weitere Algorithmen aus diesem Gebiet als Coding Challenges zu veröffentlichen. Darüber habe ich mich so gefreut, daß ich meinen geheiligten Wochenend-Hiatus unterbrechen mußte, um Euch auf dieses Video aufmerksam zu machen.

(Kommentieren)