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)2) 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, (x1, y1),…, (xn, yn), write N = "n choose 2" and consider N lines (not necessary distincts) they determine y = aijx + bij, 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 = {aij, 1<=i<j<=n}