Introduction This
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". And
finally, Thanks to a notion of approximation, we will obtain a O(nlogn)-time
algorithm (Cole, Salowe, Steiger, Szemeredi). Here a word version of the tutorial (for printing)
IMPORTANT NOTES 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.
|