The ordinary line problem revisited

Let PP be a set of n points in the plane. A connecting   line of PP is a line that passes through at least two of its points. A connecting line is called ordinary   if it is incident on exactly two points of PP. If the points of PP are not collinear then such a line exists. In fact, there are Ω(n)Ω(n) such lines (Kelly and Moser, 1958) [8]. Assuming that the points of PP are not collinear, in this note we present a new O(nlogn) algorithm for finding an ordinary line which is simpler than the two O(nlogn) algorithms presented in Mukhopadhyay et al. (1997) [10].