Calculate the fewest circles of 2r that will cover all the points marked out in a rectangle greater than 2r x 2r in size

I have a rectangle of lined graph paper of 1mm squares. The rectangle is greater than 2r in height and width. Within the rectangle I randomly mark three or more points that are no further than 2r in distance from the previous point but could be much further than 2r from other points. I have circle stickers that are all 2r in diameter. How can I calculate the best place to put my stickers to cover all the points using the least number of stickers?

I assume that when you say a circle of 2r, that is the diameter of the circle and not the radius. Proceeding with that assumption, a square with diagonal 2r fits perfectly in a circle of diameter 2r. If the diagonal of a square is 2r, you can use the Pythagorean theorem to find the side of the square. x^2 + x^2 = (2r)^2 . Solving this for x you'd get 2x^2=4r^2 so x^2 =2r^2 and x = r*sqrt(2) So if you put squares of this size next to eachother, the circles would cover all the points included inside those squares. So for a rectangle of let's say 5r by 8r, you just have to calculate how many of these squares fit into the rectangle. So 5r/r sqrt 2 = 5 sqrt 2 /2 which is approximately 3.5,so you'll need 4 squares in that direction by 8r/r sqrt 2 which is 8/sqrt 2 which is approximately 5.7, so you'd need 6 squares. So for this specific case you'd need 6*4 or 24 squares which means 24 circles. Hope this helps you out.

Hi Ira, I need to explain the question more clearly.

The problem is not to fully cover the rectangle but only cover the points in the rectangle using the least amount of circles.

Take this rectangle below

_____________

! x !

! !

! !

! y !

! !

!__z_________ !

I should be able to use just two circles if x and y and y and z are within 2r distance apart, but x and z are > 2r apart. Problem is how do I calculate that and how do I know where to place the centre of the two circles

You are correct that 2r is the diameter of the circle and thanks for the answer but I unfortunately my question was not clear enough.

## Comments