A set of n points and m line segments is given. We are given two disks of radius r. We need to place the disks in such a manner so that maximum number of points are covered. A disk covers a point only if its center and the point can be directly connected, i.e, the line joining the center of the disk and a point should not be intersected by any of the m line segments. Any ideas to solve this problem?

An idea to solving this problem can be to consider every two points in the point set. For every pair of points there can be two possible disks of radius r that touch both points. For all such combinations of disks the 2 disks covering the maximum number of points can be the answer. But will this give the right and optimal solution? For example taking the disk which covers the maximum points and then the disk which covers the second maximum points might not be the optimal answer. How to find the two disks covering the maximum points?

  • $\begingroup$ Even without a question, I think computing either a visibility graph or a planar subdivision from the the lines will almost solve this problem. $\endgroup$ – Discrete lizard Mar 21 '17 at 15:35
  • 1
    $\begingroup$ It looks like you might have accidentally created two accounts. I encourage you to merge them: cs.stackexchange.com/help/merging-accounts. That will ensure you retain access, so you can edit the question, respond to comments, and accept the best answer. $\endgroup$ – D.W. Mar 21 '17 at 16:33
  • $\begingroup$ Your idea is essentially correct, the only thing you need to look out for is that besides just covering with a disk, you also need to take the 'visibility' into account. If you don't really care about the efficiency of this, it isn't hard, but if you do want to make it efficient the terms I mentioned above can be of use. $\endgroup$ – Discrete lizard Mar 23 '17 at 10:29

Your Answer

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

Browse other questions tagged or ask your own question.