Ein Verfahren oder Algorithmus zum Auffinden der kleinsten konvexen Menge (konvexe Hülle), die eine gegebene endliche Punktmenge enthält; die konvexe Hülle ist das minimale konvexe Polygon oder Polytope, das die Punkte umschließt, und ist ein grundlegendes geometrisches Primitivelement.

Prinzip

Die konvexe Hülle lässt sich als Schnitt aller konvexen Mengen, die die Punkte enthalten, charakterisieren oder äquivalent als Menge aller konvexen Kombinationen der Punkte; Rechenmethoden nutzen Extrempunkte, Winkel-Sortierung, inkrementelle Einfügung oder Divide-and-Conquer zur Ermittlung der Hüllenspitzen.

Demonstration

Für ebene Punkte kann man die Hülle berechnen, indem man zuerst einen Extrempunkt findet, die übrigen Punkte nach Polarwinkel um diesen sortiert und einen stack-basierten Scan (z. B. Winkelscan) durchführt, der Innenpunkte verwirft, um die Reihenfolge der Hüllenspitzen eines konvexen Polygons zu erzeugen.

Fehlanwendung

Naive O(n^2)-Prüfungen zu verwenden oder Kollinearitäten und numerische Genauigkeit nicht zu behandeln, kann zu falschen Hüllen führen (fehlende Extrempunkte oder eingeschlossene Innenpunkte) oder zu instabilen Scheitelpunktanordnungen für nachgelagerte Prozesse.

Konsequenz

Korrekte Konstruktion der konvexen Hülle liefert eine minimale konvexe Ummantelung, die nützlich ist für Kollisionsdetektion, Formapproximation, Berechnung von Durchmesser und Breite und als Vorverarbeitungsschritt in vielen geometrischen Algorithmen, was oft die Problemkomplexität reduziert.

Umkehrung

Die duale Idee ist der konvexe Kern oder Schnitt der Stützhalbebenen eines Polygons; die Umkehrung des Fokus vom minimalen konvexen Obermenge auf maximale konvexe Teilmengen bzw. Kerne beleuchtet komplementäre Machbarkeits- und Sichtbarkeitsprobleme.

Abgrenzung

Gilt für endliche Punktmengen in euklidischen Räumen und verallgemeinert sich in höhere Dimensionen zu konvexen Polytope; ausgeschlossen sind unendliche Punktmengen ohne Kompaktheitsannahmen und besondere Vorsicht ist bei nicht-euklidischen Geometrien oder degenerierten kollinearen/koplanaren Konfigurationen geboten.

Semantische Spannung

Die konvexe Hülle wird manchmal mit Bounding Boxes oder anderen umschließenden Formen verwechselt; im Gegensatz zu achsengenauen Bounding-Boxen oder minimalen Flächenrechtecken ist die konvexe Hülle die kleinste konvexe Menge und kann je nach Punktverteilung beliebig viele Scheitelpunkte haben.

Synthese

Die Konstruktion der konvexen Hülle bestimmt die minimale konvexe Obermenge einer Punktmenge durch Identifikation der Extrempunkte und deren Ordnung zu einem konvexen Polytope; sie reduziert viele geometrische Fragestellungen auf Operationen an einer kleineren kombinatorischen Struktur, die die äußere Geometrie der Menge erfasst.