Sei L eine Menge nicht vertikaler Geraden in der Ebene. Gesucht ist der tiefstgelegene Punkt, der auf oder oberhalb aller Geraden in L liegt. Oder anders gesagt, wir minimieren Y unter Nebenbedingungen Y ≥ A_i*X + B_i, i = 1,... ,n.

Geben Sie einen auf randomisierter inkrementeller Konstruktion basierenden Algorithmus an, derden gesuchten tiefstgelegenen Punkt in erwarteter Zeit O(n) bestimmt.

Weisen Sie nach, dass ihr Algorithmus die geforderte Laufzeit erreicht.