2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This sound like the $k$-clique problem on disk-intersection graphs. The general $k$-clique problem is NP-hard and this restriction likely is as well. $\endgroup$ – Discrete lizard Jul 6 at 13:50
  • $\begingroup$ Although apparently there is an polynomial time algorithm for the clique problem on unit disk graphs. (See Clark, Colbourn, Johnson, Unit disk graphs ) I don't know whether it would work on general disk graphs, though. $\endgroup$ – Discrete lizard Jul 6 at 13:56
  • $\begingroup$ @Discretelizard I don't think it is $k$-clique problem.Because for example there exists $3$ circles such that each pair of them is connected but there is no common area in all of them. $\endgroup$ – Amirabbas asadi Jul 6 at 15:27
  • $\begingroup$ Hmm, yes you are correct, this is not the same problem, not every $k$-clique has common area. However, all $k$ circles that have a common area form a $k$-clique, so we can at least say that your problem is harder than finding a $k$-clique in the intersection graph. $\endgroup$ – Discrete lizard Jul 6 at 16:16
  • 1
    $\begingroup$ @Discretelizard I don't think so, see my answer. In general I think you have to be very careful about reductions from geometry to discrete logic as there are all kinds of constraints and structures you drop (triangle inequality, distance metrics, geometric theorems, etc) that can be sufficient to make an otherwise hard problem tractable. For example it is not known whether the TSP on the Euclidean plane is NP-hard or not. It might be, but you can't simply make a reduction like that. $\endgroup$ – orlp Jul 7 at 8:26
1
$\begingroup$

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.

Algorithm

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.

Complexity

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.

$\endgroup$
  • $\begingroup$ Nice answer, basically what I had in mind for my answer but actually made concrete :) $\endgroup$ – orlp Jul 7 at 20:38
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.