6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ about hackerrank.com $\endgroup$
    – vzn
    Oct 16, 2013 at 3:18
  • $\begingroup$ Please include the problem statement here, to be self-contained. Also, have you checked whether the HackerRank folks are OK with people posting solutions publicly? Is that acceptable etiquette, or is it less than desirable? $\endgroup$
    – D.W. ♦
    Oct 18, 2013 at 17:54
  • $\begingroup$ @D.W.: I edited the question statement to include the problem. I am not sure how to contact HackerRank about this, but I doubt they would care very much: this is not an ongoing contest, there are no prizes for getting a question right, and if someone is so inclined, a quick google yields coded solutions for most problems. My goal here is actually to receive some guidance, rather than a full solution. $\endgroup$
    – Dun Peal
    Oct 18, 2013 at 20:34

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ nice find, usable/relevant, although this is for facilities "near" to colinear, not the case of exactly colinear as in the problem. $\endgroup$
    – vzn
    Oct 17, 2013 at 14:58
1
$\begingroup$
  • 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.
Improve this answer
$\endgroup$
1
  • $\begingroup$ I think you're assuming the dual problem i.e. Line Cover , which is obtained by translating points to lines. Then your instance of Set Cover gives us the points to cover the lines in LC, which in turn should be translated back to lines in PC. $\endgroup$
    – Parham
    Oct 17, 2013 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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