I am given N Points with integer co-ordinates and two integer D , M ; All the given points will be in one side of y = M straight line . I need to find The minimum number of guard placed on y = M line (with integer x coordite ), so that all the N points is at most D euclidian distance away from the guards... Like
1 1
2 2
3 1
These are 3 points. I am given D = 2 , M = 0;
Then Minimum Number of guard needed is 1. placed in (2,0) coordinate.
N = 10^4
We can think in reverse.
For each point P, determine the interval on the y = M line that satisfies the constraint of the Euclidean distance <= D.
Then the problem transforms into a classic problem of minimum clique cover in interval intersection graph, which can be solved efficiently.