Given centers, find minimum radius for set of circles such that they fully cover another

6
votes

I have the following geometry problem: You are given a circle with the center in origin - C(0, 0), and radius 1. Inside the circle are given N points which represent the centers of N different circles. You are asked to find the minimum radius of the small circles (the radius of all the circles are equal) in order to cover all the boundary of the large circle.

The number of circles is: 3 ≤ N ≤ 10000 and the problem has to be solved with a precision of P decimals where 1 ≤ P ≤ 6.

For example:
N = 3 and P = 4

and the coordinates:
(0.193, 0.722)
(-0.158, -0.438)
(-0.068, 0.00)

The radius of the small circles is: 1.0686.

I have the following idea but my problem is implementing it. The idea consists of a binary search to find the radius and for each value given by the binary search to try and find all the intersection point between the small circles and the large one. Each intersection will have as result an arc. The next step is to 'project' the coordinates of the arcs on to the X axis and Y axis, the result being a number of intervals. If the reunions of the intervals from the X and the Y axis have as result the interval [-1, 1] on each axis, it means that all the circle is covered.

In order to avoid precision problems I thought of searching between 0 and 2×10P, and also taking the radius as 10P, thus eliminating the figures after the comma, but my problem is figuring out how to simulate the intersection of the circles and afterwards how to see if the reunion of the resulting intervals form the interval [-1, 1].

Any suggestions are welcomed!

2
calgorithmgeometrycomputational-geometry
Are you saying which circle of the 3-10000 will require the smallest radius to cover the original circle? Or are you using all 3-10000 circles at one time to cover the original circle? – jamesbtate
Your algorithm only looks at the circle's circumference, but it's possible that the whole circumference is covered while there is uncovered area in the middle. – interjay
@puddingfox. You have to use all the smaller circles in order to cover the original one. – ZLMN
I don't think your example solution can possibly be correct. The radius of the "large circle" is given as 1, so making the "small circles" also radius 1 would satisfy the problem in your example. 1 might not be minimal, but it is definitely better than 1.0686. – Don Roby
@interjay - well, in the document where the OP translated and copied this from, it says cover the circle, and not its area. I should also say that this is from an on-going romanian computer science contest that ends in about 30 hours, for whoever this may concern. – IVlad

2 Answers

2
votes

Each point in your set has to cover the the intersection of its cell in the point-set's voronoi diagram and the test-circle around the origin.

To find the radius, start by computing the voronoi diagram of your point set. Now "close" this voronoi diagram by intersecting all infinite edges with your target-circle. Then for each point in your set, check the distance to all the points of its "closed" voronoi cell. The maximum should be your solution.

It shouldn't matter that the cells get closed by an arc instead of a straight line by the test-circle until your solution radius gets greater than 1 (because then the "small" circles will arc stronger). In that case, you also have to check the furthest point from the cell center to that arc.

0
votes

I might be missing something, but it seems that you only need to find the maximal minimal distance between a point in the circle and the given points.

That is, if you consider the set of all points on the circle, and take the minimal distance between each point to one of the given points, and then take the maximal values of all these - you have found your radius.

This is, of course, not an algorithm, as there are uncountably many points.

I think what I'll do would be along the line of:

  1. Find the minimal distance between the circumference and the set of points, this is your initial radius R.
  2. Check if the entire circle was covered, like so: For any two points whose distance from each other is more than 2R, check if the entire segment was covered (for each point, check if the circle around it intersects, and if so, remove that segment and keep going). That should take about o(N^3) (you iterate over all of the points for each pair of points). If I'm correct (though I didn't formally prove it) the circle is covered iff all of the segments are covered.
  3. Of all the segment which weren't covered, take the long one, and add half it's length to R.
  4. Repeat.

This algorithm will never cover the circle per se, but it's easy to prove that it exponentially converges to a full cover, so it should be able to find the needed radius with arbitrary accuracy within a reasonable amount of iterations.

Hope that helps.