Determinar si un círculo está cubierto por algún conjunto de otros círculos

Question

Supongamos que tienes un conjunto de círculos $\mathcal{C} = \{ C_1, \ldots, C_n \}$ cada uno con un radio fijo $r$ pero con coordenadas de centro variables. Luego, se te da un nuevo círculo $C_{n+1}$ con el mismo radio $r$ que los círculos anteriores pero con una nueva coordenada de centro.

¿Cómo puedes determinar si el área cubierta por $C_{n+1}$ está completamente cubierta por $\mathcal{C}$?

¿Cómo hacer esto si los círculos pueden tener radios variables?

Nota: Todavía no he podido encontrar una solución matemática elegante para esto. Viniendo de la informática, lo mejor que se me ocurrió es resolver esto de una manera brutal y fea usando algún tipo de muestreo de Monte Carlo, es decir, dibujar una gran cantidad de puntos aleatorios del área de $C_{n+1}$ y luego verificar para cada punto si está incluido por lo menos en un círculo en $\mathcal{C}_{\text{intersecante}}$ (subconjunto de $\mathcal{C}$ con círculos que están dentro de $2r$ de $C_{n+1}$).

Answer 1

Creo que el trabajo de Herbert Edelsbrunner sobre las alpha shapes podría tener cierta relevancia, aunque cuando lo estaba leyendo estaba principalmente interesado en aplicaciones para determinar volúmenes y áreas de superficie, por lo que no estoy seguro si la pregunta precisa que estás haciendo está abordada. Consulta los papers aquí en su sitio web, quizás comenzando con el paper: H. Edelsbrunner. The union of balls and its dual shape. Discrete Comput. Geom. 13 (1995), 415-440.

El resumen de ese paper:

Se describen algoritmos eficientes para calcular propiedades topológicas, combinatorias y métricas de la unión de finitas bolas esféricas en $\mathbb{R}^d$. Estos algoritmos se basan en un complejo simplicial dual a una descomposición de la unión de bolas usando celdas de Voronoi, y en fórmulas de inclusión-exclusión cortas derivadas de este complejo. Los algoritmos son más relevantes en $\mathbb{R}^3$ donde las uniones de finitas bolas son comúnmente utilizadas como modelos de moléculas.

Creo que la idea principal es básicamente la sugerida por Anton Petrunin.

Answer 2

Su pregunta parece equivalente a construir un "diagrama de Voronoi ponderado aditivamente" o "diagrama de Apolonio". Puede buscar en Google cualquiera de los dos, pero el artículo fundamental es el de Franz Aurenhammer (Diagramas de Voronoi - Una encuesta de una estructura de datos geométricos fundamentales es un buen lugar para buscar). La cosa se puede construir en tiempo polinomial, y las búsquedas deberían ser logarítmicas (aunque no estoy 100% seguro).

Answer 3

Aquí hay una solución matemática "bastante básica" a tu problema, que funciona en tiempo $n^3$, pero programarlo es bastante fácil, es cuestión de 1 hora.

Al principio desechamos cualquier $C_i$ ($1\leq i\leq n$) que no se intersecte con $C_{n+1}.

También descartamos cualquier $C_i$ ($1\leq i\leq n$) que esté dentro de otro $C_j$ ($1\leq j\leq n$).

Desde ahora consideramos "sombras lunares" $L_{i}=C_{n+1} \cap C_{i}$, donde $1\leq i\leq n$. Algunas $L_i$ pueden seguir siendo iguales a $C_i$ completo, por supuesto.

El problema inicial es entonces equivalente a lo siguiente: ¿es $C_{n+1}$ igual a la unión $U=\cup_{i=1,\ldots, n} L_i$?

Lo reformularemos de esta manera: ¿es el borde $\partial U$ igual al círculo de borde $\partial C_{n+1}$? Para verificar esto hacemos lo siguiente:

Verificación 0) Verificamos el borde exterior $\partial C_{n+1}$. Para hacer eso, encontramos todos los puntos $p_j$ que $\partial C_i$ ($1\leq j\leq n$) corta en $\partial C_{n+1}$. Luego ordenamos todos estos puntos por su coordenada angular en $\partial C_{n+1}$, obteniendo puntos ordenados $t_j$ ($j=1,\ldots,K\leqslant 2n$). Y luego para cada $j=1,...,K$ verificamos el punto medio del segmento $[t_j,t_{j+1}]$ -- si pertenece a algún círculo $C_i$ con $1\leq i\leq n. Por supuesto, también verificamos el punto medio de$[t_K,t_1]$. Si algún punto medio falla, entonces hemos terminado, y este punto no está cubierto.

Si no, continuamos y verificamos si $\partial U$ no contiene puntos dentro de $C_{n+1}. Hacemos eso con:

Verificaciones 1...n) Son exactamente similares a la Verificación 0, pero consideramos el arco $A_j$ de $C_j$ que está dentro de $C_{n+1}$ como el segmento de verificación. Así que nuevamente encontramos los puntos que $C_i$ secciona en $C_j$ dentro de $A_j, incluyendo además los extremos de$A_i. Luego ordenamos estos puntos hasta la coordenada angular de $C_j$ y verificamos los puntos medios -- si cada uno está cubierto por algún círculo. Si una de estas verificaciones falla, encontramos puntos no cubiertos. Si todas las verificaciones tienen éxito, entonces $C_{n+1}$ está cubierto.

P.D. Usando el sencillo algoritmo $n \log n$ para calcular la unión de segmentos en el borde de un círculo, se puede reducir la complejidad a $n^2 \log n$.