{"ID":2826936,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.17268","arxiv_id":"2512.17268","title":"Line Cover and Related Problems","abstract":"We study extensions of the classic \\emph{Line Cover} problem, which asks whether a set of $n$ points in the plane can be covered using $k$ lines. Line Cover is known to be NP-hard, and we focus on two natural generalizations. The first is \\textbf{Line Clustering}, where the goal is to find $k$ lines minimizing the sum of squared distances from the input points to their nearest line. The second is \\textbf{Hyperplane Cover}, which asks whether $n$ points in $\\mathbb{R}^d$ can be covered by $k$ hyperplanes. We also study the more general \\textbf{Projective Clustering} problem, which unifies both settings and has applications in machine learning, data analysis, and computational geometry. In this problem, one seeks $k$ affine subspaces of dimension $r$ that minimize the sum of squared distances from the given points in $\\mathbb{R}^d$ to the nearest subspace. Our results reveal notable differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable when parameterized by $k$, we show that Line Clustering is W[1]-hard with respect to $k$ and does not admit an algorithm with running time $n^{o(k)}$ unless the Exponential Time Hypothesis fails. Hyperplane Cover has been known to be NP-hard since the 1980s, following work of Megiddo and Tamir, even for $d=2$, we show that it remains NP-hard even when $k=2$. Finally, we present an algorithm for Projective Clustering running in $n^{O(dk(r+1))}$ time. This bound matches our lower bound for Line Clustering and generalizes the classic algorithm for $k$-Means Clustering ($r=0$) by Inaba, Katoh, and Imai [SoCG 1994].","short_abstract":"We study extensions of the classic \\emph{Line Cover} problem, which asks whether a set of $n$ points in the plane can be covered using $k$ lines. Line Cover is known to be NP-hard, and we focus on two natural generalizations. The first is \\textbf{Line Clustering}, where the goal is to find $k$ lines minimizing the sum...","url_abs":"https://arxiv.org/abs/2512.17268","url_pdf":"https://arxiv.org/pdf/2512.17268v2","authors":"[\"Matthias Bentert\",\"Fedor v. Fomin\",\"Petr A. Golovach\",\"Souvik Saha\",\"Sanjay Seetharaman\",\"Kirill Simonov\",\"Anannya Upasana\"]","published":"2025-12-19T06:33:30Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}