The ordinary line problem revisited. (English) Zbl 06045870
Summary: Let \(\mathcal P\) be a set of n points in the plane. A connecting line of \(\mathcal 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 \(\mathcal P\). If the points of \(\mathcal P\) are not collinear then such a line exists. In fact, there are \(\varOmega (n)\) such lines (Kelly and Moser, 1958) [8]. Assuming that the points of \(\mathcal P\) are not collinear, in this note we present a new \(O(n \log n)\) algorithm for finding an ordinary line which is simpler than the two \(O(n \log n)\) algorithms presented in Mukhopadhyay et al. (1997) [10].
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
References:
| [1] | Artin, E., Geometric Algebra (1957), Interscience: Interscience New York · Zbl 0077.02101 |
| [2] | Coxeter, H., A problem of collinear points, Amer. Math. Monthly, 55, 26-28 (1948) |
| [3] | Coxeter, H., Introduction to Geometry (1969), J. Wiley and Sons · Zbl 0181.48101 |
| [4] | Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer-Verlag · Zbl 0634.52001 |
| [5] | Erdos, P., Problem 4065, Amer. Math. Monthly, 50, 65 (1943) |
| [6] | Gallai, T., Solution to problem 4065, Amer. Math. Monthly, 51, 169-171 (1944) |
| [7] | Hadwiger, H.; Debrunner, H.; Klee, V., Combinatorial Geometry in the Plane (1964), Holt, Rinehart and Winston Inc.: Holt, Rinehart and Winston Inc. New York |
| [8] | Kelly, L. M.; Moser, W. O.J., On the number of ordinary lines determined by \(n\) points, Canad. J. Math., 10, 210-219 (1958) · Zbl 0081.15103 |
| [9] | Motzkin, T., The lines and planes connecting the points of a finite set, Trans. Amer. Math. Soc., 70, 451-464 (1951) · Zbl 0043.14603 |
| [10] | Mukhopadhyay, A.; Agrawal, A.; Hosabettu, R. M., On the ordinary line problem in computational geometry, Nordic J. Comput., 4, 4, 330-341 (1997) · Zbl 0893.68160 |
| [11] | Steinberg, R., Three point collinearity, Amer. Math. Monthly, 51, 169-171 (1944) |
| [12] | Sylvester, J. J., Mathematical questions 1851, Educational Times, 59, 98 (1893) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
