3
$\begingroup$

Given a set of n points, and a number k decide whether there exist k straight lines such that all of the points are covered. Here a point is covered by a line if that point lies on that line.

I can formulate an ILP for the same. The problem seems to be hard. I want to formally prove its NP-Completeness.

Note that, for k=1, the problem is in P. Simply find the liner regression/line fitting and test whether the error is zero. Even when k=2, the problem still seems to be hard. Is it really so? And what about the general case? What are the candidate problems for the reduction?

$\endgroup$

3 Answers 3

6
$\begingroup$

The general case of this problem is NP-complete, as shown by Meggido and Tamir [N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Oper. Res. Lett., 1:194–197, 1982.]. Their reduction is from 3SAT, in the usual way: some points in the construction represent clauses, others variables, which are all carefully arranged together with some additional points such that the relation between clauses and variables in 3SAT is represented in the instance. I suggest you read the paper for more details.

Note that if $k$ is constant the problem can be solved in polynomial time: we only need to consider the lines that contain at least two of our points, of which there are $O(n^2)$. So, there are only $O( {n^2 \choose k})=O(n^{2k})$ sets of lines we need to test, which can be done in $O(n)$ time for each set, giving an algorithm that takes $O(n^{2k+1})$ time in total.

While the brute-force approach above is already polynomial for a constant $k$, there are better algorithms. In fact, this problem is fixed parameter tractable in $k$: Afshani et al. give an algorithm with a $O^*((Ck/\log k)^{k})$ time algorithm, where $C$ is some constant and the $O^*(\cdot)$ notation ignores polynomial factors. However, this particular algorithm may not be very practical. Depending on the application, formulating this problem as an ILP or set cover instance can be more efficient.

$\endgroup$
1
  • $\begingroup$ If you pick the start and end point of each line, you may be able to reduce the possibilities. The left most point is the start of the first line. The second is either the end point of the first line (meaning it contains no other points) or the start of the second line etc. after finding the start points, we assign end points. $\endgroup$
    – gnasher729
    Commented Apr 3, 2023 at 7:51
4
$\begingroup$

Consider all pairs of points in turn and detect all those that are collinear with them. This takes time $O(n^3)$ and will generate up to $\dfrac{(n-1)n}2$ subsets. This reduces the question to a set cover decision problem.


For $k=2$, an easy solution in $O(n)$ is given by @JohnL: Pick $3$ points. One of the lines must cover $2$ of them. Check if the remaining $n−2$ points are collinear. (More precisely $n-m$, removing all points collinear with the first two.)

$\endgroup$
0
1
$\begingroup$

As pointed out in this answer, the problem is hard. Moreover the problem is infact APX-hard (see here). Also, the problem is commonly known as the point-line-cover (PLC) in the literature.

This does infact provide an interesting insight by showing an easy reduction to set-cover problem which is well studied and have a simple simple greedy algorithm that has a $\log n$ approximation factor (see here) or a factor $f$ where $f$ is frequecy of an element in the subsets (see here).

A practical approach for problem can be as follows: apply one of the approximation schemes mentioned above, let us call it $\mathcal{A}$. Let $k'$ be the number of subsets returned by $\mathcal{A}$. If our input $k$ for the set-cover decision problem with $k \ge k'$, we return 'yes'. While if $k\log n < k'$ return 'no'. Otherwise we apply brute-force or some FPT scheme mentioned here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.