Recently in a contest I came across this question :
"Given N circles, defined by their x co-ordinate, y co-ordinate and radius r, remove the minimum number of circles such that the remaining circles are non intersecting. Touching a circle is also considered as intersecting."
1 ≤ N ≤ 1000
0 ≤ abs(X), abs(Y), abs(R) ≤ 1000
The setter solution used a greedy solution (to remove the circle with maximum intersections everytime till all remaining are non intersecting), but this fails on a very simple test case.
Here, the greedy solution gives answer as 4, but we can do it by removing 3 circles also.
I could convert this problem into a graph (edges depict intersection between the vertices) for which we need the minimum vertex cover, which doesn't have a polynomial time solution. Can we convert it into some other problem and solve efficiently? What's the best complexity you can come up with ?