Points-in-a-plane from HackerRank

Question

I've been struggling with this problem for days now, making no progress:

There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your goal is to remove all the points in the least number of turns. Given the coordinates of the points, calculate two things:

• The minimum number of turns (T) needed to remove all the points.
• The number of ways to to remove them in T turns. Two ways are considered different if any point is removed in a different turn.

-- https://www.hackerrank.com/challenges/points-in-a-plane

I've tried a greedy exhaustive solution, where I draw a line between each pair of points, then start to eliminate the lines in descending order based on the number of points they cross. Unfortunately, there is at least one case where this approach produces suboptimal results:

For ease of discussion, I will call lines "longer" or "shorter", based on how many points they include. The greedy algorithm is simply to eliminate lines in order of descending length.

Suppose we have a set of N longer lines, and another set of M shorter lines. Our greedy algorithm will eliminate the long lines first. But what if every single point of the long lines is also included in a short line? In that case,our initial elimination of the N longer line was a waste, since we would have gotten those lines "for free" had we just eliminated the shorter lines. Specifically, our greedy approach will require N + M eliminations, where we could have cleared all points in just M steps.

The simplest example input demonstrating this is:

(0, 1), (1, 2), (2, 4), (3, 3)
(0, 0), (1, 0), (2, 0), (3, 0)
(0,-1), (1,-2), (2,-4), (3,-3)

As you can see, we have a line of length 4 running along the X axis, and 4 shorter vertial lines of length 3 perpendicular to it. Our greedy algorithm will first eliminate the longest line, after which there will be 8 sets of points remaining, with no more than 2 of them collinear. Eliminating those will thus take 4 steps, for a total 5, where we could have eliminated all points in just 4 steps, had we simply eliminated the 4 vertical lines first.

Could someone provide at least a hint at the general body of knowledge required to approach this? I solved many other HackerRank questions, but can't make any headway with this one.

Answer 1

this is the problem of covering points with lines or linear facility location which is NP-Hard. This is why you couldn't find a greedy solution. There are approximation and exact algorithms for this problem. If you want an exact algorithm that is efficient on large inputs I suggest you a simple version of parametrized solution for this problem.

Answer 2

• find all the [sets of] colinear points. create an array of them, or basically an array of arrays. each is a set. there seems to be a polynomial bound of lines in terms of points. (exercise: prove it)
• solve with set cover. set cover was one of the original NP-complete problems discovered by Karp 1972. NP completeness is the "general body of knowledge required to approach this". there are indeed "greedy" algorithms for this problem but note that greedy algorithms are generally not "exhaustive" because they get stuck in local minima.