Dual
Problem
Given
n points_{ }(x_{1}, y_{1}),…, (x_{n},
y_{n}). We assume that the points are in general position, that
means that no three points are colinear and that no two of the induced
lines have the same slope.This assumption symplify the problem without
affecting the complexity of the algorithms. To make progress in designing selection algorithms, we transform the slope selection problem into a more convenient form using point-line duality. This
is defined by a mapping T that takes the point p = (a,b) to the line Tp
given by y=ax+b and the line l given by y = cx+d to the point (-c,d).
T preserves incidence. Under T, the n given points map to lines l_{1},…, l_{n }whose points of intersection , l_{i} inter l_{j }=_{ }(u_{ij },v_{ij}), correspond to the lines incident with ith and jth original points. Furthermore -u_{ij} is the slope of this line. Thus the dual of the problem of selecting slope k is the following, equivalent selection problem: Given
distinct l_{1},…, l_{n}, lines, find the intersection
point whose x-coordinate is the N-k+1th smallest element of the set TS
= {u_{ij}, 1 <= i< j<=
n}. Now,
we will consider the general problem of selecting elements in TS. We write t_{1}<…<t_{N} for the N elements of TS. The ti's are distinct because the input points are in general position. Given k, we seek t_{k.}_{} |