Matrix.code's blog

Simple Geometry
By Matrix.code, 9 years ago, In English

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
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply