AbstractLet

Pbe a set ofnpoints in the plane. Aconnectingline ofPis a line that passes through at least two of its points. A connecting line is calledordinaryif it is incident on exactly two points ofP. If the points ofPare not collinear then such a line exists. In fact, there areOmega(n)such lines. In this paper, we present twoO(nlogn)time algorithms for finding an ordinary line, assuming that the points ofPare not collinear. We also present an optimalO(ntime algorithm for finding all such ordinary lines.^{2})

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling

Additional Key Words and Phrases: computational geometry, ordinary line, parametric searching

Selected papers that cite this one

- Olivier Devillers and Asish Mukhopadhyay. Finding an Ordinary Conic and an Ordinary Hyperplane.
Nordic Journal of Computing, 6(4):462-467, Winter 1999.

Selected references

- Richard Cole. Slowing down sorting networks to obtain faster sorting algorithms. Journal of the ACM, 34(1):200-208, January 1987.

- Richard Cole, Micha Sharir, and Chee K. Yap. On
k-hulls and related problems. SIAM Journal on Computing, 16(1):61-77, February 1987.

- Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, October 1983.