Enumerating Collinear Points in Higher Dimensions

Abstract

In this paper, we study the problem of reporting all maximal collinear subsets of a point set $S$ in $\mathbb{R}^d$ for $d \ge 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(dn^2 \log n)$, and one with space complexity $O(n^2)$ and time complexity $O(d^2n^2)$.

Keywords

• Collinear points
• Degeneracy testing
• Maximal collinear subsets