Encontrar el círculo mayor que contiene un solo punto en un conjunto (y ningún otro punto)

Question

Dado un delimitada $A \times B$ rectángulo con un conjunto de coordenadas elegido, por ejemplo, genera con el comando:

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

Para cada punto en randPoints, me gustaría encontrar el centro y el radio del círculo más grande que contiene el punto, pero ningún otro punto de la randPoints conjunto, y no exceder de los límites de la $A \times B$ cuadro.

¿Cómo podría hacer esto en Mathematica v9.0? En el ejemplo, hay 10^4 puntos, pero también estoy imaginando mucho más grandes conjuntos, por lo que idealmente me gustaría una rápida rutina. Esto podría, sin embargo, constituyen empujar mi suerte.

El problema es trivial si uno bloquea el centro del círculo en el elemento relevante en randPoints (sólo el uso de la Nearest función para encontrar el radio del círculo), pero me parece un truco adicional es necesaria si sólo se requiere de este elemento por sí mismo en algún lugar en el interior del círculo.

Answer 1

Deje que el punto que nos interesa el círculo para contener ser $\mathbf p_0$, y el resto de los puntos se $\mathbf p_1, \ldots, \mathbf p_n$. Si el círculo está centrado en $\mathbf q$, la más grande de la radio se puede tener es $$r(\mathbf q) = \min_{i=1}^n\|\mathbf q-\mathbf p_i\|.$$ Para el círculo para contener $\mathbf p_0$, tenemos $\|\mathbf q-\mathbf p_0\|\le r(\mathbf q)$, que si se conecta en la definición de $r(\mathbf q)$ sólo significa que $\mathbf q$ está más cerca de a $\mathbf p_0$ que cualquier otro $\mathbf p_i$; en otras palabras, se encuentra en la celda correspondiente a $\mathbf p_0$ en el diagrama de Voronoi de $\{\mathbf p_0, \mathbf p_1, \ldots, \mathbf p_n\}$. Así pues, nuestro problema se reduce a encontrar el máximo de $r(\mathbf q)$ dentro de la celda de Voronoi de $\mathbf p_0$, que voy a llamar a $C$.

Hay dos posibilidades: o bien el máximo se encuentra en el interior de $C$, o se encuentra en su límite. En el primer caso, debe ser un sin restricciones máximo local de $\min_{i=1}^n\|\mathbf q-\mathbf p_i\|$; el máximo es un vértice del diagrama de Voronoi de $\{\mathbf p_1,\ldots,\mathbf p_n\}$. En el último caso, si $\mathbf q$ se encuentra en un borde, siempre se puede aumentar el $r(\mathbf q)$ moviendo a lo largo del borde, por lo que el máximo debe ocurrir en un vértice de $C$.

Por lo tanto, aquí es un algoritmo:

1. Construir el diagrama de Voronoi $\mathcal V$$\{\mathbf p_0,\mathbf p_1,\ldots,\mathbf p_n\}$.
2. Deje $C$ ser la célula de $\mathcal V$ correspondiente a $\mathbf p_0$.
3. Evaluar $r(\mathbf q)$ de todos los vértices de $C$.
4. Construir el diagrama de Voronoi $\mathcal V'$$\{\mathbf p_1,\ldots,\mathbf p_n\}$. (No debe existir algoritmos eficientes para la eliminación de un solo punto de $\mathbf p_0$ a partir de una previamente calculada diagrama de Voronoi $\mathcal V$.)
5. Evaluar $r(\mathbf q)$ en todos los vértices de $\mathcal V'$ que se encuentran dentro de $C$.
6. Elija el punto de los pasos 3 y 5 con el mayor $r(\mathbf q)$. El círculo deseado ha de centro $\mathbf q$ y radio de $r(\mathbf q)$.

Notas de implementación: Desde que usted quiere hacer esto para cada punto, uno por uno, no tienes que repetir el paso 1, que debería ser el más caro de paso. También, en los pasos 3 y 5, ya tiene un diagrama de Voronoi, de manera que pueda evaluar $r(\mathbf q)$ sin iterar sobre todos los $n$ puntos.

Answer 2

Esto no es eficiente pero funciona:

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

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

Show[lp, Graphics[gr]]

donde lp es laListPlot