Finding the largest circle that contains a single point in a set (and no other point)

Question

Given a bounded $A \times B$ rectangle with a set of chosen coordinates, generated for example with the command:

A = 1;
B = 1;
randPoints = Table[{RandomReal[{0,A}],RandomReal[{0,B}]},{k,1,10^4}];
ListPlot[randPoints] 

For each point in randPoints, I would like to find the center and radius of the largest circle that contains that point but no other point from the randPoints set, and does not exceed the boundaries of the $A \times B$ box.

How might one do this in Mathematica v9.0? In the example there are 10^4 points, but I'm also envisioning much larger sets, so ideally I'd like a fast routine. This could, however, constitute pushing my luck.

The problem is trivial if one locks the center of the circle on the relevant element in randPoints (just use the Nearest function to find the circle radius), but it seems like an additional trick is required if one only requires this element to be by itself somewhere inside the circle.

Answer 1

Let the point we want the circle to contain be $\mathbf p_0$, and the other points be $\mathbf p_1, \ldots, \mathbf p_n$. If the circle is centered at $\mathbf q$, the largest radius it can have is $$r(\mathbf q) = \min_{i=1}^n\|\mathbf q-\mathbf p_i\|.$$ For the circle to contain $\mathbf p_0$, we need $\|\mathbf q-\mathbf p_0\|\le r(\mathbf q)$, which if you plug in the definition of $r(\mathbf q)$ just means that $\mathbf q$ is closer to $\mathbf p_0$ than any other $\mathbf p_i$; in other words, it lies in the cell corresponding to $\mathbf p_0$ in the Voronoi diagram of $\{\mathbf p_0, \mathbf p_1, \ldots, \mathbf p_n\}$. So, our problem reduces to finding the maximum of $r(\mathbf q)$ within the Voronoi cell of $\mathbf p_0$, which I'll call $C$.

There are two possibilities: either the maximum lies in the interior of $C$, or it lies on its boundary. In the former case, it must be an unconstrained local maximum of $\min_{i=1}^n\|\mathbf q-\mathbf p_i\|$; any such maximum is a vertex of the Voronoi diagram of $\{\mathbf p_1,\ldots,\mathbf p_n\}$. In the latter case, if $\mathbf q$ lies on an edge, you can always increase $r(\mathbf q)$ by moving along the edge, so the maximum must occur at a vertex of $C$.

So, here is an algorithm:

1. Construct the Voronoi diagram $\mathcal V$ of $\{\mathbf p_0,\mathbf p_1,\ldots,\mathbf p_n\}$.
2. Let $C$ be the cell of $\mathcal V$ corresponding to $\mathbf p_0$.
3. Evaluate $r(\mathbf q)$ for all vertices of $C$.
4. Construct the Voronoi diagram $\mathcal V'$ of $\{\mathbf p_1,\ldots,\mathbf p_n\}$. (There should exist efficient algorithms for removing a single point $\mathbf p_0$ from a previously computed Voronoi diagram $\mathcal V$.)
5. Evaluate $r(\mathbf q)$ at all vertices of $\mathcal V'$ that lie inside $C$.
6. Choose the point from steps 3 and 5 with the largest $r(\mathbf q)$. The desired circle has center $\mathbf q$ and radius $r(\mathbf q)$.

Implementation notes: Since you want to do this for each point one by one, you don't have to repeat step 1, which ought to be the most expensive step. Also, in steps 3 and 5, you already have a Voronoi diagram, so you can evaluate $r(\mathbf q)$ without actually iterating over all $n$ points.

Answer 2

This is not efficient but works:

near = {#, Nearest[randPoints, #, 2][[2]]} & /@ randPoints;

gr = {Red, Circle[#[[1]], 0.99 EuclideanDistance[#[[1]], #[[2]]]]} & /@
    near;

Show[lp, Graphics[gr]]

where lp is the ListPlot