Maximum Enclosing Circle of a Given Radius

Question

I try to find an approach to the following problem:

Given the set of point $S$ and radius $r$, find the center point of circle, such that the circle contains the maximum number of points from the set. The running time should be $O(n^2)$.

At first it seemed to be something similar to smallest enclosing circle problem, that easily can be solved in $O(n^2)$. The idea was to set an arbitrary center and encircle all point of $S$. Next, step by step, replace the circle to touch the left/rightmost points and shrink the circle to the given radius, obviously, this is not going to work.

Answer 1

I don't know how to solve this problem in $O(n^2)$ time, but an $O(n^2\log n)$ algorithm does exist.

Let $C(s_i)$ be the circle whose center is $s_i$, the $i$-th point, with radius $r$. It's not hard to find that the point set $P = \{p_0, p_1, \ldots, p_m\}$ can be enclosed by a circle with radius $r$ iff the intersection $I(P)$ of $C(p_0), C(p_1), \ldots, C(p_m)$ is not empty. Moreover, if $I(P)$ is not empty, there must be some points in $I(P)$ lay on some $\textbf{bd}C(p_i)$ (the boundary of $C(p_i)$). So for each $C(s_i)$ and each point $p$ on its bondary, we try to find how many circles contain $p$. The max count among all $p$ will be the answer to this problem.

Let's examine points in $\textbf{bd}C(s_i)$. There is an one-to-one mapping between the points on $\textbf{bd}C(s_i)$ and the real number in $[0, 2\pi)$. For each circle $C(s_j)$, the intersection between $C(s_j)$ and $\textbf{bd}C(s_i)$ can be represented by an interval $[begin_j, end_j]$. So for all circles other than $C(s_i)$, there are at most $n-1$ intervals (some circles may not intersect with $C(s_i)$). The max count can be found easily by sorting all $2(n-1)$ end points of interval, scanning them in order and counting the current overlapping number. For each $C(s_i)$, this step can be done in $O(n\log n)$ time, and there are $n$ such circles, so the time complexity of this algorithm is $O(n^2\log n)$.

Answer 2

I think the difficult questions is knowing whether the circle you've selected is actually "maximal" within the set. The only way I can think to determine this is to try all the possible combinations of the points, and test the size of the circle which encloses them.

You can reduce the search space though by first dividing the point space into a grid of square cells with width 2r. Then locate the cell with the greatest density. Since you've already located one circle of X points you can conclude that if a circle exists with more points, then it must have at least X points in it. And use this as a starting off point for testing the different combinations of the points.

If you are only looking for a set of points which is likely to be maximal, then you might be able to further reduce the number of combinations you need to test by selecting those points which fall within a neighborhood of cells where the density of the neighborhood is greater than X.

Having said this, both "reductions" can can fail, and at the worst case you will be computing circles for all possible combinations of points.

Answer 3

In Chazelle, B.; Lee, D. T. 's paper Computing 36, 1-16(1986), theorem 3 in page 15, it states that the maximum enclosing circle finding algorithm takes $O(n^2)$ time cost.

I think the key is still the $O(n^2)$ intersection graph construction algorithm it mentions early, (or see Edelsbrunner, H. (1987), Algorithms in Combinatorial Geometry, chapter 7). Afterwards the maximun enclosing circle finding should be straightforward.

Apparently, this problem is equivalent to find the point covered by maximum number of given circles and it is easily to know only those mostly $2n^2$ points intersected by given n circles need to be considered as candidates. (This also leads a $O(n^2log(n))$ algorithm directly )

However, by utilizing the above mentioned $O(n^2)$ construction algorithm, it leads an $O(n^2)$ algorithm for this problem, too. Because the intersection graph constructed with vertices as intersection points and edges as arcs is an Euler planar graph. So one can just travel all the arcs through an Euler cycle and an order of arcs indexed by the indexes of circles it belongs to and information of whether any arc is a "leaving away arc" (curved backwards) or "entering into arc" (curved forwards) for the met-during-travling vertice which this arc is incident on will be recorded.

By Jordan's theorem an intersection vertice is enclosed by a circle only if it meets a "leaving away arc" belonging to that circle first or has an incident arc belonging to that circle. So after the whole travel, the maximum enclosing circle can be easily found. It is simliar to the case of deciding the covering times for points with ordered intervals along a straight line, (or i.e. the 1D version of this enclosing problem), except the order has already been given by the travel. While by Euler's formular $V + E - F = 2$ for a planar graph, the total number of arcs is linear with the number of vertices, and since one does not need to record related information again when traveling back to vertices already visited, by handshaking lemma, the total time cost will be $O(n^2)$.