Maximum Enclosing Circle of a Given Radius

Problem Detail: 

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.

Asked By : com

Answered By : Wu Yin

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1825