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?