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
Posted: Thu Jul 14, 2022 2:06 pm
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.
Prove that your algorithm achieves the required runningtime.