Given the centers, find the minimum radius for many circles so that they completely cover the other

Question

I have the following geometry problem: You are given a circle with a center of origin - C (0, 0) and a radius of 1. Inside the circle, there are N points that represent centers from N different circles. You will be asked to find the minimum radius of the small circles (the radius of all circles is equal) to cover the entire border of the large circle.

The number of circles: 3 ≤ N ≤ 10000, and the problem should be solved up to ten-digit numbers, where 1 ≤ P ≤ 6.

For instance:
N = 3 and P = 4

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

The radius of small circles is 1.0686.

I have the following idea, but my problem is its implementation. The idea is a binary search to find the radius and for each value given by the binary search, to try to find the entire intersection point between the small circles and the large one. Each intersection will have an arc. The next step is to “project” the coordinates of the arcs on the X axis and Y axis, resulting in several intervals. If the reunions of the intervals from the X and Y axis result in the interval [-1, 1] on each axis, this means that the whole circle is covered.

To avoid accuracy issues, I was thinking about searching between 0 and 2 & times; 10 ^P and also taking the radius as 10 ^P , thereby excluding the numbers after the comma, but my problem is how to simulate the intersection of circles, and then how to see, reconnecting the resulting intervals is the interval [-1, 1].

Any suggestions are welcome!

Answer 1

Each point in your set should cover the intersection of its cell in the holographic point diagram and the test circle around the origin.

To find the radius, start by calculating the voronoi diagram of your set of points. Now close this voronoi diagram by crossing all infinite edges with your target circle. Then, for each point in your set, check the distance to all points of its “closed” voronoi cell. Maximum should be your decision.

It doesn’t matter that the cells are closed by an arc instead of a straight line using a test circle until your solution radius is greater than 1 (because then the "small" circles will be stronger). In this case, you also need to check the farthest point from the center of the cell to this arc.

Answer 2

Maybe something is missing for me, but it seems to you that you only need to find the maximum minimum distance between a point in a circle and these points.

That is, if you consider the set of all points on the circle and occupy the minimum distance between each point to one of the given points, and then take the maximum values ​​of all these values, you find your radius.

This, of course, is not an algorithm, since there are countless points.

I think I will do the line:

• Find the minimum distance between the circle and the set of points, this is your initial radius R.
• Check if the whole circle is closed, for example: For any two points whose distance from each other exceeds 2R, check if the entire segment has been covered (for each point, check if the circle intersects around it, and if so, delete this segment and continue traffic). This should take about o (N ^ 3) (you iterate over all points for each pair of points). If I am right (although I have not officially proven this), the circle is covered if all segments are covered.
• From the entire segment that has not been covered, take a long one and add half its length to R.
• Repeat

This algorithm will never cover the circle as such, but it is easy to prove that it converges exponentially to a full shell, so it should be able to find the required radius with arbitrary accuracy within a reasonable number of iterations.

Hope this helps.