HEIR_OF_SLYTHERIN's blog

By HEIR_OF_SLYTHERIN, history, 6 weeks ago, In English

Question: You are given N circles, with ith represented by coordinates of centre as xi,yi and radius ri(all circles lie on the xy plane). The task is to remove minimum number of circles such that the remaining circles do not overlap or touch each other.
Note: Ci, Cj are overlapping is the distance between their centre points <=ri+rj.
Constraints:
2<=N<=1000
0<=xi,yi,ri<=10000
Input format:
First line contains N
The next N lines contains three integers xi,yi,ri.
Sample input:
3
0 0 3
2 0 3
4 0 3
Sample output
2

Any help in algo or idea is appreciated. Thanks in Advance.

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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Link?

This looks like an NP-hard problem, unless there are some other constraints you haven't mentioned.

The underlying graph structure is a superset of unit disk graphs, and I'm 99% sure minimum vertex cover on this graph remains NP-hard.

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Firstly, we can find which circles are overlapping by checking as per the given condition. This can be done easily in $$$O(N^2)$$$ time complexity. We can assume the circles to be nodes of a graph, where $$$C_i$$$ and $$$C_j$$$ have an edge between them if they are intersecting. With this, we can also maintain the degree (number of edges) for each node.

Now, we can greedily remove the nodes with the highest degree and subsequently reduce the degree of the connected nodes by $$$1$$$. We can do this until the degree for every node becomes $$$0$$$. This can be done using a priority queue or set. The number of nodes removed is the answer.

Hope it makes sense.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This won't work.

    Consider a path graph of 5 vertices. If your algorithm somehow picks the middle vertex as the first to remove, it will produce 3 as the answer, but 2 is actually optimal.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    here(in the gfg article) all centres are aligned on the x-axis right??

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The solution explained in this article is wrong. Consider following case:

    c[] = {2, 5, 5}
    r[] = {3, 1, 2}
    

    Answer is 1, but the solution gives 2.