What's the problem?

What’s the problem?

Given n points in the plane and an integer k:

We want to select the pair of points that determines the line with the kth smallest slope.

Time of the algorithm which will be computed

For general k the parametric search technique (Megiddo) gives an O(n(logn)²) algorithm. This is modified to produce an optimal O(nlogn)-time selection algorithm by incorporating an approximation idea.

Remark:When k=O(n), line sweeping gives an optimal, O(nlogn) algorithm.

Formulation of the problem

Given n distincts points in the plane, (x₁, y₁),…, (x_n, y_n), write N = _{"n choose 2"} and consider N lines (not necessary distincts) they determine y = a_ijx + b_ij, where 1<=i<j<=n, one for each pair of points.

Chazelle mentions the problem of selecting one of these lines according to the rank of its slope : given 1<=k<=N, we seek the kth smallest element of S = {a_ij, 1<=i<j<=n}