4
$\begingroup$

In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666.

The algorithm chooses each point p from a set S and then subdivides it into k-lines.

This can be seen as a special case of set cover. All points (each p belongs to P) are in a cartesian plane, and the algorithm needs to find if they can be covered by k lines (where each line l belongs to L). This image below clarifies it further:

Point-line-cover

My question is around what is written in the paper linked above at page 666 regarding where is p taken from: At some point during the text it says "Otherwise, the algorithm chooses an element p ∈ S'". However, further down in the algorithm it says "choose p ∈ S" (without the prime symbol).

Is p taken from S or S' (S prime)?

Thanks!

$\endgroup$
  • $\begingroup$ Hi @arch-wilhes, about your suggested edit, certainly point-line-cover relates to set cover but it's not the same problem as it is a more restricted version. Thus I believe I should not rename it as they are different. This other paper shows a more specific description of the point-line-cover problem, including drawings (it also references the above paper by Langerman and Morin which my question is about). $\endgroup$ – testTester Sep 6 '15 at 10:23
  • $\begingroup$ Good point. But just a suggestion, it is often better to include more info in your post (e.g. pointing out that it is a special case of set cover problem: many of us here will know immediately what you are talking about if you say "set cover problem"). This would help anyone who is not familiar with the subject but may be able to answer your question, and thus increasing the question's probability of being answered. $\endgroup$ – 吖奇说 Sep 6 '15 at 12:06
  • $\begingroup$ Thanks a lot for the feedback. I edited it, hopefully it is clearer now. $\endgroup$ – testTester Sep 6 '15 at 12:41
6
$\begingroup$

The algorithm should say "choose $p \in S'$", that is, the text is the correct version, rather than the pseudocode.

Note how the algorithm works:

  • $S',S_{1},\ldots,S_{k}$ form a partition of $S$ (i.e. every element of $S$ is in exactly one of $S',S_{1},\ldots,S_{k}$).
  • At each step it chooses which $S_{i}$ to put $p$ into.
  • Initially $S' = S$, and $S_{i} = \emptyset$ for all $i$.

So $S'$ is the set of points that still need to be covered, and $S_{i}$ is the set of points covering by hyperplane $i$, in some abstract sense. Thus the algorithm, at each iteration, picks an uncovered element from $S'$, and puts it in some $S_{i}$.

Interestingly, this error made it all the way to the journal version.

$\endgroup$
  • 1
    $\begingroup$ It's funny when you are just learning something and, of course, the last thing you can think of is that the paper is wrong... This proves I am not crazy! hahaha.. Thanks! $\endgroup$ – testTester Sep 7 '15 at 10:51

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.