Konvexe Hülle per Divide&Conquer

Sortiere die Punkte nach x-Koordinat’,
dann ist die Aufgab’ reichlich fad’.
Zerlege die Menge in zwei gleiche Teile,
sodass der Computer sich tüchtig beeile.
Vollführe dies so lange bis
du im Basisfalle bist.
Sodann ein Dreieck du erzeugst,
an dem du dich gar prächtig freust.
Hat eine Meng’ zu wenig Punkt’,
so scheint das zwar recht ungesund,
ist bei genauerem Betrachten
aber kein Grund, sie zu verachten.
In diesem Falle nämlich ist
die Abarbeitung wirklich trist.
Ein Punkt oder auch eine Streck’
sind ohne Weiteres konvex.

Ist dies getan, ein schöner Baum
beschreibt den Rekursionssuchraum.
Wiedervereinigung ist toll,
und die Vollziehung würdevoll.
Wie schon aus früh’rem Teil bekannt,
liegt das Verfahren auf der Hand:
Vereinige zwei Polygone
umhüllt von der konvexen Zone,
ganz fix in linearer Zeit,
und hüll’ sie in ihr Kurvenkleid.
Sodann fahr’ fort mit dieser Tour,
und schau dabei scharf auf die Uhr:
Das Mastertheorem zeigt leicht,
dass die Schranke wird erreicht.
O(n log n) ist zwar nicht viel,
doch in vergleichsbasiertem Stil
ist das Sortier’n von Punkten möglich
in dieser Zeit - Ist das nicht löblich?
Die Summe zweier Asymptoten
entspricht nun, wie ein jeder weiß,
gerade ihrem Maximum,
womit die Aufgab’ nun zum
wohlverdienten Ende kommt
und man sich in Punkten sonnt.
— Louis Lutzweiler und Fabian Richter