trainor@lanai.cs.ucla.edu (Vulture of Light) (04/06/88)
Hey all you, stop posting and read Guy Jacobson's message. It is very
informative. The optimal algorithm is O(n). You can also read about
Megiddo's algorithm in SIAM J. Comput. 12(4), 759-776 (Nov. 1983).
New problem:
Given N line segments in the plane, give an algorithm for determining
a line that passes through all of them, or state that it does not exist.