0

Problem: Find two circles with smallest area to cover all the given finite points on Cartesian plane. Each circle should cover at least two points.

For the simpler problem, when we need to find just one circle to cover all the given points, I know we can solve this optimization problem for given points $x$ and some circle with center at $x_c$ and radius $r$:

\begin{array}{ll}\min\limits_{{r:\,||x-x_c||_2\leq r}} r.\end{array}

For the original problem, we need to minimize $r_1^2+r_2^2$, i.e., $||r||_2$ for $r=[r_1 \quad r_2]$. I am confused what should be the constraint, how to write that either $||x-x_{c_1}||_2\leq r_1$ or $||x-x_{c_2}||_2\leq r_2$ should hold and that each circle should cover at least two points?

Lee
  • 1,910
  • 12
  • 19
  • Can you sort out the references to balls and points consistently and do you mean disks in the plane or 3D balls covering points in the plane, and tell us if there are a finite or infinite number of (points ?) – Tom Collinge Sep 25 '19 at 08:25
  • @TomCollinge I have edited the question, let me know if it is still unclear – Lee Sep 25 '19 at 08:34
  • 1
    Do you want to minizime the sum of the area of the two disks or the total area covered by the two disks? That is does the area of intersection of the two disk count twice or just once? – quarague Sep 25 '19 at 09:15
  • @quarague I want to make their total area minimum, the intersection counts once only. I think my objective function may not be correct in this case – Lee Sep 25 '19 at 09:27

1 Answers1

0

I will answer my own question, I manage to find an algorithm for the computational purpose. Maybe will be useful for someone.

We can use the following idea to solve the problem:

i) Create a circle from each given point and slowly increase the radius of each circle.

ii) If any two circles intersect, replace them with one new circle. This new circle will have center in the middle of the line connecting centers of the original two circles.

iii) Repeat (ii) until only 2 circles left.

iv) If circle has only one point inside, increase it until it touches any other point.

You can try to code it, it works!

Lee
  • 1,910
  • 12
  • 19