2026-10-01T07:51:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25502 2026-09-23T23:42:06Z ddc:004 open_access

Line Cover and Related Problems Bentert, Matthias Fomin, Fedor V. Golovach, Petr A. Saha, Souvik Seetharaman, Sanjay Upasana, Anannya Point Line Cover Projective Clustering W-hardness XP algorithm We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Fedor V. Fomin and Petr A. Golovach and Souvik Saha and Sanjay Seetharaman and Anannya Upasana 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.13 urn:nbn:de:0030-drops-255023 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode