website aims to show how we can transform a problem of slope selection
to a problem of ranking x-coordinates.
Here, we will give a first algorithm which resolve the problem thanks
to a sweeping method (Shallow method).
Then, a general selection algorithm which has a complexity of O(n(logn)2) will be built thanks to the principle of "Parametric Search".
finally, Thanks to a notion of approximation, we will obtain a O(nlogn)-time
algorithm (Cole, Salowe, Steiger, Szemeredi).
I used the paper written by Cole, Salowe, Steiger, Szemeredi, to build this site.
Parametric Search: The general selection algorithm uses the principle of Parametric Search developped by Megiddo in the late 1970s. The principle of parametric search is to compute a value a* that answers to an equation with the use of an algorithm that solves the corresponding decision problem. The decision can be state as follows: given a value a, decide whether a<a*, a=a*, or a>a*. In our case, we use the dual problem to build the decision problem.