On the ordinary line problem in computational geometry
Asish Kumar Mukhopadhyay, Alok Agrawal, Ravi Hosabettu · 1997
Let P be a set of n points in the plane. A connecting line of P 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 P. If the points of P are not collinear then such a line exists. In fact, there are Ω(n) such lines. In this paper, we present two O(n log n) time algorithms for finding an ordinary line, assuming that the points of P are not collinear. We also present an optimal O(n2) time algorithm for finding all such ordinary lines.