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, (x_{1}, y_{1}),…, (x_{n},
y_{n}), write N = _{"n choose 2"} and
consider N lines (not necessary distincts) they determine y = a_{ij}x
+ 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}
