Randomisierter Inkrementelle Konstruktion

Erste Frage Aufrufe: 187     Aktiv: 13.07.2022 um 11:55

0

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.

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
0 Antworten