Let L be a set of non-vertical straight lines in the plane. We are looking for the lowest point lying on or above all st

[answerhappygod]

Let L be a set of non-vertical straight lines in the plane. Weare looking for the lowest point lying on or above all straightlines in L. Or in other words, we minimize Y under constraints Y ≥ A_i*X + B_i=1,...,n Specify an algorithm based on randomized incremental constructionthat candetermines the searched lowest point in expected timeO(n).
Prove that your algorithm achieves the required runningtime.