0

I have an enclosed rectangle with dimensions l x w in the plane with N circles with centers (a,b) (different for each point). How could you calculate the smallest shared radius for the circles so all the points in the plane are within at least one circle.

KReiser
  • 65,137
William Freedman
  • 1

2 Answers2

0

A simple approach is to use a hexagonal grid. If the centers are spaced $1$ unit apart the radius is $\frac 1{\sqrt 3}$ and each circle is responsible for a regular hexagon of side $\frac 1{\sqrt 3}$ and area $\frac 3{2\sqrt 3}$. Divide the area of your rectangle by this and you get an approximation, valid for large $N$, of the number of circles required. To calculate the radius of the circles, divide the area of the rectangle by $N$ and by this constant to get the area of the circle.

For small numbers of circles, the packings become irregular and computing the minimal number of circles is an unsolved problem. You can look at packomania.com for circles in a square to get an idea. This is packing circles, but you can expand them to get coverage. The best configuration may be different.

Ross Millikan
  • 374,822
  • I think I have the opposite problem. I have a set amount of points and need to find the minimum radius, not the amount of circles with a given radius. – William Freedman Jul 04 '20 at 02:56
  • That was the point of my last sentence in the first paragraph. You start with the area of the rectangle and $N$ and get the area of the circle. From the area you use $r=\sqrt{\frac A\pi}$. See how it covers and you may need a few more around the edges. – Ross Millikan Jul 04 '20 at 02:58
0

Given points $(a_i,b_i)$ for $i\in\{1,\dots,N\}$, you want to find a point $(x,y)$ in the rectangle such that $(x,y)$ is furthest away from the closest point. Let $r$ denote the desired common radius. The problem is to maximize $r$ subject to \begin{align} r^2 &\le (x-a_i)^2 + (y-b_i)^2 &&\text{for all $i$} \\ x &\in [0,\ell] \\ y &\in [0,w] \end{align}

RobPratt
  • 45,619
  • How did you get that? (Just for my own understanding) – William Freedman Jul 04 '20 at 03:10
  • I pictured the circles growing simultaneously until all points are covered. The last point covered is the one that furthest away from the closest $(a_i,b_i)$. – RobPratt Jul 04 '20 at 03:12
  • @WilliamFreedman, do you have a particular set of points in mind? – RobPratt Jul 04 '20 at 03:42
  • I was trying to find a way to get the radius given the points. I'm writing a program that would use this to find the minimum radius for cell tower-like objects. – William Freedman Jul 04 '20 at 17:17
  • Given the points, you can use a nonlinear (quadratically constrained) programming solver to find the radius. Alternatively, if you have a way to check whether there exists an uncovered point $(x,y)$ for a given $r$, you can perform a bisection search for the smallest $r$ that covers every $(x,y)$.. – RobPratt Jul 04 '20 at 18:09