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.