Algorithmus der Woche
Gift-Wrapping Algorithmus
Berechnung der konvexen Hülle mit dem Jarvis-March-Verfahren
Theoretischer Hintergrund
Definition: Die konvexe Hülle einer Punktmenge P ist die kleinste konvexe Menge, die alle Punkte aus P enthält.
Zeitkomplexität
O(n·h)
Worst Case
O(n²)
Raumkomplexität
O(h)
Steuerung
Punkte
0
Hüllpunkte
0
Laufzeit
0ms
Effizienz
–
Hinweis:
Klicken Sie auf die Zeichenfläche, um Punkte manuell zu platzieren, oder nutzen Sie “Punkte generieren” für zufällige Datensätze. Der Algorithmus findet die äußeren Punkte, die eine konvexe Hülle bilden.
Referenz: Jarvis, R. A. (1973). “On the identification of the convex hull of a finite set of points in the plane”. Information Processing Letters, 2(1), 18-21.