I have N circles with different radius and position in the plane. The problem is finding k circles which have a common area.Obviously this can be solved using Brute-Force in $O(N^k)$. Is there a more efficient way to do such query?
This problem and related problems have been studied in the paper "Bajaj, C., & Li, M. (1983). On the duality of intersections and closest points. Cornell University."
They call a common area for $k$ circles a '$k$-intersection'. The paper gives an $O(n^2\log n)$ algorithm for the problem of finding a $k$-intersection when the circles have different radius. (Theorem 13) It is not clear to me from the paper how that bound is achieved, but I do see how to achieve $O(n^3)$ time with their approach.
The main idea is to construct the following (directed) planar intersection graph $G=(V,E,F)$: The vertices $V$ of this graph are all intersection points of the circles and the edges $E$ are the circle arcs connecting those intersection points. The direction of the edges is counterclockwise on the circle, such that the interior of the circle it is part of lies to the left of the edge. We also keep track of the faces $F$ of this planar graph, which are the regions enclosed by the edges $E$.
Note that each region of circle intersections corresponds to a face of this planar graph and that the number of circles that contain the region is equal to the number of clockwise boundary edges of the corresponding face. If we have computed $G$, then we can maintain a counter for each face in $F$ and traverse the graph to visit all edges and increase the counter of face left of each edge. Then, after we have traversed the edges, each face has the number of circles that contain it stored in the counter.
Since there can be at most $O(n^2)$ intersections of $n$ circles, $|V|=O(n^2)$. Since $G$ is a planar graph, $|E|\leq 3|V|-6 =O(n^2)$. So, traversing the graph takes $O(|V|+|E|)=O(n^2)$ time.
As for constructing the graph, the authors claim that this graph can be constructed in $O(n^2\log n)$ time by sorting the edges. I did not see any further explanation of this in the paper and do immediately see how to achieve this. (in particular, it would be helpful to know on what they sort.)
I do see how to do this in $O(n^3)$: The vertices and edges of the graph can be constructed in $O(n^2)$ time by iteratively adding new circles. When a new circle is added, we add the new intersection points and subdivide some of the existing edges.
Adding the faces is more complicated and I currently only see the naive method of for each edge $e$, traversing all edges that are on the boundary of the two faces adjacent to edge $e$. This takes $O(n)$ per edge, so $O(n^3)$ in total. It does seem like we can do better here, but I currently don't see how.
$O(n^2\log n)$ is good, but can we do better? For the case where the circles all have the same radius, this is possible: Chazelle and Lee have found an $O(n^2)$ time algorithm based on an implicit traversal through the intersection graph ("Chazelle, B. M., & Lee, D. T. (1986). On a circle placement problem. Computing, 36(1-2), 1-16."). Whether $O(n^2)$ is possible for the case with circles of different radius they leave as an open problem, which has remained open for now, as far as I'm aware.
I don't believe this problem is NP-hard, due to a simple observation: the maximum number of regions formed by $N$ circles is A014206 which is $O(N^2)$. You can just keep track of and iterate over each region with smart computational geometry formed by circle arcs, choose an arbitrary point in each region and check if $k$ circles contain that point.
This is not easy to program (computational geometry is complex), but should be on the order of $O(N^3)$ or $O(N^4)$. But perhaps someone comes up with a better algorithm.