Connecting Circles

Правка en2, от 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.

Теги computational geometry, help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Newtech66 2020-05-18 16:22:18 0 (published)
en1 Английский Newtech66 2020-05-18 16:21:09 1192 Initial revision (saved to drafts)