# Fit of two lines to an arbitrary set of points - NP-Hardness

My problem is:

Given $$n$$ points in $$\mathbb{R}^d$$, I want to find a partition of these $$n$$ points into $$k=2$$ clusters. For each cluster, instead of computing the centroid as in the usual k-means problem, I construct the one-dimensional subspace (what I call a line) minimizing the sum of squared distances between the points of the cluster and the line. So, overall, I want to find a partition such that the total sum of the squared distances between each point and the best line going through its cluster is minimized.

For the usual k-means problem, I know that there exists a polynomial algorithm when $$d$$ and $$k$$ are fixed, and is NP-hard when one of the two is part of the input.

Related to this problem, after asking this question on cs.stackexchange (a particular case when $$d=2$$), I came across this question on stackoverflow where we can read this sentence in the validated answer:

it's well known that finding a globally optimal fit for even two lines to an arbitrary set of points is NP-Hard as it can be reduced to k-means clustering

My question concerns the quote above: Does anyone know a reference to this reduction claimed to be well-known?

After lots of research and attempts to build it myself, I am not able to find such a reduction.

• Could you please make the question self contained. What is the objective function you are trying to minimize. Commented Jul 2, 2023 at 20:11
• I suggest you start by doing some research to understand the claims about NP-hardness of k-means clustering, e.g., cs.stackexchange.com/q/153074/755, stats.stackexchange.com/q/396965/2921, stackoverflow.com/q/18634149/781723, then try to formulate your problem in a self-contained and precise/mathematical way (what is the objective function you are trying to minimize?), then try to come up with such a reduction.
– D.W.
Commented Jul 2, 2023 at 22:21
• @InuyashaYagami The objective function is the sum of the squared distances. Commented Jul 2, 2023 at 22:56
• @D.W. I clarified my problem but my question is more about the quote claiming the reduction is well-known although I did not find any trace of it. Commented Jul 2, 2023 at 22:58
• I don't know how to build such a reduction other, and I too am questioning whether one exists. But perhaps understanding how k-means clustering was proven NP-hard would give some ideas for reduction strategies to prove your problem NP-hard (even if it doesn't have a direct reduction from k-means clustering).
– D.W.
Commented Jul 2, 2023 at 23:02