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.
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.
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.
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.
My bad. Didn't consider this case.
https://www.geeksforgeeks.org/minimum-circles-needed-to-be-removed-so-that-all-remaining-circles-are-non-intersecting/
The solution explained in this article is wrong. Consider following case:
Answer is 1, but the solution gives 2.
it might be very obvious, but how is answer 1 in your example?
It seems that the GFG article is using the wrong term and talking about intersecting discs, not circles.
Anyone has any idea? stuck pretty much for ages!!
It's NP-hard, don't waste time on it. The author likely had a wrong solution. Any greedy you read is wrong.
From the circle packing theorem you can see that the resulting intersection graph is an arbitrary planar graph. The problem is thus just vertex cover on a planar graph, which is well-known to be NP-hard.
(It's not technically a rigorous proof because we only have finite integer coordinates, but I think anyone would agree it's unlikely that it makes a difference)
Since the x,y, and r are in the range of 10000 can't we look in that direction of solving for each x or each y? can't figure out the actual solution but N=1000 might be a bait making us to think only in N^2 ,It might be in N*max(x,y)
You could in theory have something with $$$max(x,y)$$$ in its complexity even if the problem is NP-hard, because that's not technically polynomial.
However, I find it hard to believe that such a solution exists, since the problem seems too closely related to vertex cover, which is NP-Complete even for planar graphs with maximal degree of 3.
For this to be solvable in reasonable time would imply that there's something fundamentally stopping you from converting an arbitrary 3-degree planar graph vertex cover problem to a solvable instance of this problem. The only way for this to be true is if somehow the reduction may yield exponentially large coordinates, which I just doubt.
If you're keen go ahead and try to come up with solutions of this nature — I have not given a concrete proof that it's impossible, but I believe it to be so.