Nordic Journal of Computing Bibliography

Asish Mukhopadhyay, Alok Agrawal, and Ravi Mohan Hosabettu. On the Ordinary Line Problem in Computational Geometry. Nordic Journal of Computing, 4(4):330-341, Winter 1997.
Abstract

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 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

Selected references


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database