Introduction

This
website aims to show how we can transform a problem of slope selection
to a problem of ranking x-coordinates.

The ranking problem enables us, for example, to see what's the kth smallest
statue (see the Russian dolls)..

Here, we will give a first algorithm which resolve the problem thanks
to a sweeping method (Shallow method).

This is a O(n(logn) + k(logn)) algorithm.

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.*