Newtech66's blog

Connecting Circles
By Newtech66, history, 5 years ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

(bump)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints?

The cost to connect 2 circles is $$$d - r_1 - r_2$$$, where $$$d$$$ is the distance between the centers and $$$r_1$$$ and $$$r_2$$$ are the radios.

If number of circles is small enough, the problem is reduced to first finding the components and then performing a minimum spanning tree, where the cost of an edge is 0 if they originally belong to the same component.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As I said, I gave no constraints because I have no idea what the solution might be.

    I thought of the same solution with MST but if the radius of one circle is increased, the distance to all of its neighbours decreases by the same amount, so the edges aren't "independent" (??), so as to speak, and I thought that means we can't use the classic MST approach. If this is your solution, can you provide a proof of correctness too?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, indeed. I hadn't considered that. You would need to recalculate costs after expanding a circle, but it will depend on the constraints whether that will fit time limit or not.

      → Reply