Published in Volume XXIX, Issue 1, 2019, pages 81–100, doi: 10.7561/SACS.2019.1.81

Authors: A.G. Rudi, R.A. Rufai

Abstract

In this paper, we study the problem of reporting all maximal collinear subsets of a point set S in Rd for d≥3. An algorithm for this problem can be used to detect if any three of the points are collinear or find the line that intersects the most points in S. Besides, obtaining such maximal subsets is necessary for some problems about the collinearity relation among points, such as when covering them with the fewest lines. We present practical algorithms to find all maximal collinear subsets of a set of n points, including one with space complexity O(n) and time complexity O(dn2log n), and one with space complexity O(n2) and time complexity O(d2n2 ).

Keywords: Collinear points, Degeneracy testing, Maximal collinear subsets.

Full Text (PDF)

References

[1] P. Afshani, T.M. Chan. Optimal Halfspace Range Reporting in Three Dimensions. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 180–186, 2009. doi:10.1137/1.9781611973068.21.

[2] P. K. Agarwal, J. Erickson. Geometric Range Searching, Its Relatives. In B. Chazelle, J.E. Goodman, R. Pollack (Eds.) Advances in Discrete and Computational Geometry, 1–56, 1999. doi:10.1090/conm/223/03131.

[3] T. Asano, N. Katoh. Variants for the Hough Transform for Line Detection. Computational Geometry: Theory and Applications 6(4), 231–252, 1996. doi:10.1016/0925-7721(95)00023-2.

[4] H. Brnnimann, B. Chazelle, J. Pach. How Hard is Half-Space Range Searching. Discrete & Computational Geometry 10(2), 143–155, 1993. doi:10.1007/BF02573971.

[5] B. Chazelle, L.J. Guibas, D.T. Lee. The Power of Geometric Duality. BIT Numerical Mathematics 25(1), 76–90, 1985. doi:10.1109/sfcs.1983.75.

[6] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. Springer, 2008. doi:10.1007/978-3-662-04245-8.

[7] H. Edelsbrunner, L.J. Guibas. Topologically Sweeping an Arrangement. Journal of Computer and System Sciences 38(1), 165–194, 1989. doi:10.1016/0022-0000(89)90038-X.

[8] H. Edelsbrunner, J. O’Rourke, R. Seidel. Constructing Arrangements of Lines and Hyperplanes with Applications. SIAM Journal on Computing 15(2), 341–363, 1986. doi:10.1137/0215024.

[9] J. Erickson. New Lower Bounds for Convex Hull Problems in Odd Dimensions. SIAM Journal on Computing 28(4), 1198–1214, 1999. doi:10.1137/S0097539797315410.

[10] J. Erickson, R. Seidel. Better Lower Bounds on Detecting Affine and Spherical Degeneracies. Discrete & Computational Geometry 13(1), 41–57, 1995. doi:10.1007/BF02574027.

[11] V. Froese, I. Kanj, A. Nichterlein, R. Niedermeier. Finding Points in General Position. International Journal of Computational Geometry & Applications 27(4), 277–296, 2017. doi:10.1142/S021819591750008X.

Bibtex

@article{sacscuza:rudi2019ecphd,
  title={Enumerating Collinear Points in Higher Dimensions},
  author={A. G. Rudi, R. A. Rufai},
  journal={Scientific Annals of Computer Science},
  volume={29},
  number={1},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2019},
  pages={81–100},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2019.1.81}
}