AbstractLet 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 Omega(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.
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.