Connecting Circles

Revision en2, by Newtech66, 2020-05-18 16:22:18

The problem:

Assume there are $n$ circles on the plane. The $i^{th}$ circle has an initial radius $r_i$ $(r_i \geq 0)$. We are allowed to increase or decrease the radius of the $i^{th}$ circle by $1$ unit at a cost $c_i$ $(c_i > 0)$. Let us make a graph such that each circle is a node, and there is an undirected edge between two circles $C_i$ and $C_j$ if their intersection is not empty (just to be clear, the cases are: they touch internally/externally, they intersect at two points, one lies inside the other).

Find the minimum cost to make the graph connected.

Source:

Trying to think of new and interesting problems and then creating this problem which I can't solve at all. The inspiration here was from radio stations. Every radio station has a coverage radius, and if we make the network connected, a message can travel between any two radio stations.

I have given up on this problem. I would appreciate it if someone can enlighten me on how to solve this problem or with any restrictions on it (eg. "$r_i=0$", "All $c_i$ are equal", etc).

Time complexity required:

Anything works, I haven't even been able to figure out an approach.

History

Revisions

Rev. Lang. By When Δ Comment
en2 Newtech66 2020-05-18 16:22:18 0 (published)
en1 Newtech66 2020-05-18 16:21:09 1192 Initial revision (saved to drafts)