[Solved]: Points-in-a-plane from HackerRank

Problem Detail: 

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.

Asked By : Dun Peal

Answered By : Mahmoud A.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16111