Point covering problem

Question

I recently had this problem on a test: given a set of points m (all on the x-axis) and a set n of lines with endpoints [l, r] (again on the x-axis), find the minimum subset of n such that all points are covered by a line. Prove that your solution always finds the minimum subset.

The algorithm I wrote for it was something to the effect of: (say lines are stored as arrays with the left endpoint in position 0 and the right in position 1)

algorithm coverPoints(set[] m, set[][] n):
    chosenLines = []
    while m is not empty:
        minX = min(m)
        bestLine = n[0]
        for i=1 to length of n:
            if n[i][0] <= minX and n[i][1] > bestLine[1] then
                bestLine = n[i]
        add bestLine to chosenLines
        for i=0 to length of m:
            if m[i] <= bestLine[1] then delete m[i] from m
    return chosenLines

I'm just not sure if this always finds the minimum solution. It's a simple greedy algorithm so my gut tells me it won't, but one of my friends who is much better than me at this says that for this problem a greedy algorithm like this always finds the minimal solution. For proving mine always finds the minimal solution I did a very hand wavy proof by contradiction where I made an assumption that probably isn't true at all. I forget exactly what I did.

If this isn't a minimal solution, is there a way to do it in less than something like O(n!) time?

Thanks

Arondell

I'm having trouble following your pseudocode. What is n[i][0] <= m supposed to mean if n[i][0] is a point on the x axis and m is a set? Can you clarify a bit and maybe explain naturally what your idea is? By set do you mean a sorted collection or any collection? On what criteria do you order n? – Santoro

Sorry about that, I meant <= minX. Edited. I should have probably used the word array instead of set as well for the inputs. It's ordered in that the elements can be accessed sequentially, but not in the sense that the points are in ascending or descending order. All inputs are randomly ordered, I assumed. The gist of my algorithm was: working from the left, find the line of longest length that covers the first uncovered point and add it to the collection. Repeat until every point is covered. – Arondell

Consider the points 1, 100, 101, 102, 103, 104 and the lines [1, 100] [10, 101] [20, 102] [30, 103] [40, 104] [101, 104]. If I understand your algorithm correctly, it'll choose [1, 100] to cover the first two points, [10, 101] to cover the third, up to [40, 104] to cover the last. We can do much better by choosing [1, 100] and [101, 104] or [1, 100] and [40, 104]. If I understood your algorithm correctly, then it won't work on all cases. – Santoro

@IVlad: No, as I understand the algorithm, it will choose the segment that covers the current point and has the largest right point . In fact it will return [1, 100] , [101,104]. However, the algorithm has a little bug I think. Initializing bestLine to n[0] may not be the right thing to do. – Karyolymph

Answer 1

Your greedy algorithm IS correct. We can prove this by showing that ANY other covering can only be improved by replacing it with the cover produced by your algorithm.

Let C be a valid covering for a given input (not necessarily an optimal one), and let S be the covering according to your algorithm. Now lets inspect the points p1, p2, ... pk, that represent the min points you deal with at each iteration step. The covering C must cover them all as well. Observe that there is no segment in C covering two of these points; otherwise, your algorithm would have chosen this segment! Therefore, |C|>=k. And what is the cost (segments count) in your algorithm? |S|=k.

That completes the proof.

Two notes:

1) Implementation: Initializing bestLine with n[0] is incorrect, since the loop may be unable to improve it, and n[0] does not necessarily cover minX.

2) Actually this problem is a simplified version of the Set Cover problem. While the original is NP-complete, this variation results to be polynomial.

Karyolymph

Sounds good, thanks for the help. I did forget to cover the case where it isn't possible to cover the points with the given lines though, you're right. – Arondell

Answer 2

Hint: first try proving your algorithm works for sets of size 0, 1, 2... and see if you can generalise this to create a proof by induction.

Rieger