Near-optimal algorithms for point-line fitting problems

We study the {\sc Rich Lines} problem, which is a fundamental point-line fitting problem in computational geometry. In this problem, the input is a set $S$ of points in the plane, and the goal is to compute the set of all lines that each covers at least $\lambda$ points from $S$, for a given integer parameter $\lambda \geq 2$; this problem subsumes the {\sc 3-Points-on-Line} problem and the {\sc Exact Fitting} problem, which---the latter---asks for a line containing the maximum number of points. The {\sc Rich Lines} problem has been extensively studied, and its solution serves as a building block for several algorithms in computational geometry. We present a randomized Monte Carlo algorithm for {\sc Rich Lines} that achieves a lower running time than the current-best algorithm of Guibas et al.~[{\it Computational Geometry} 1996], for a wide range of the parameter $\lambda$. We derive lower-bound results showing that, for $\lambda =\Omega(\sqrt{n \log n})$, the upper bound on the running time of this randomized algorithm matches the lower bound that we derive on the time complexity of {\sc Rich Lines} in the algebraic computation trees model.
Journal of Computational Geometry, Vol. 13 No. 1 (2022)