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.


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.

Tags computational geometry, help


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