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

Ver esta pregunta anterior de MO. La unión de n discos (representada en términos de sus arcos límite) se puede construir en tiempo $O(n\log n)$. Así que construya la unión de los $n$ discos que le dieron, y construya por separado la unión de los $n+1$ discos incluyendo el que quiere cubrir. El disco dado está cubierto si y solo si las dos uniones son iguales.

Answer 2

Si $n$ no es demasiado grande (digamos, menos de $10^4$), y me enfrentara realmente a implementar el cálculo, podría elegir este simple algoritmo $O(n^2)$. Sea $R_i$ la región cubierta por el disco objetivo (delimitada por $C_{n+1}$) menos los discos delimitados por $C_1, C_2, \ldots, C_i$. $R_i$ es una colección de regiones delimitadas por arcos circulares. No sería difícil implementar el paso genérico de restar el disco delimitado por $C_{i+1}$ de las regiones en $R_i$, intersectando $C_{i+1}$ con cada arco que conforma el límite de $R_i$.
     
La razón por la que este algoritmo es cuadrático es que $\partial R_i$ es $O(n)$. Esto no es obvio, pero fue establecido en un artículo por János Pach y Micha Sharir, "Sobre el Límite de la Unión de Conjuntos Convexos Planos," Geometría Discreta y Computacional, Volumen 21, Número 3, 1999, 321-328. (Enlace al artículo.)

Answer 3

Intentaría usar los dominios de Voronoi $$V_i=\{\,x\in\mathbb R^2\mid |o_i-x|\le |o_j-x|^2\ \text{para todo}\ j\,\},$$ donde $o_i$ es el centro de $C_i. Supongo que hay algunos algoritmos que lo producen. Luego solo necesitas verificar que

• cada vértice $a\in C_{n+1}$ del dominio de Voronoi $V_i$.
• y cada punto de intersección $\partial V_i\cap \partial C_{n+1}$

esté en $C_i$.

En el caso de radios variables, aún puedes usar dominios de Voronoi modificados; $$V_i=\{\,x\in\mathbb R^2\mid f_i(x)\le f_j(x)\ \text{para todo}\ j\,\}.$$ donde $f_i(x)$ es la potencia del punto $x$ con respecto a $C_i$.

P.D. Eliminé mi respuesta anterior ya que calculé mal el tiempo; pensé que llevaría mucho tiempo. Pero Alexander Griffing señaló que es $O(n{\cdot}log n)$ --- un diagrama de Voronoi ver wikipedia y solo se necesitan verificar $O(n)$ puntos después de hacer el diagrama.

Answer 4

Esto se puede hacer usando una subdivisión recursiva del plano por cuadrados no superpuestos. Comienza con un cuadrado lo suficientemente grande como para incluir todos los círculos. Luego se puede dividir esto en cuatro cuadrados de la mitad de la longitud del borde, dividir cada uno de esos en cuatro y así sucesivamente. Si llevamos un registro de qué cuadrados están dentro de cuáles cuadrados más grandes, terminamos con una estructura de datos llamada un quadtree. Vamos a construir recursivamente un quadtree hasta que encontremos un cuadrado que esté completamente dentro de $C_{n+1}$ y completamente fuera de todos los demás círculos, o encontremos un conjunto de cuadrados que cubran $C_{n+1}$ y estén dentro de uno o más de los otros círculos. Para un cuadrado dado y un círculo dado, es cuestión de geometría de secundaria decidir si el cuadrado está completamente dentro del círculo, completamente fuera de él o en el límite. Para cada cuadrado lo comparamos con todos los círculos, y recursivamente seguimos: si está completamente dentro de $C_{n+1}$ y completamente fuera de todos los demás círculos, devolvemos 'falso'. De lo contrario, si el cuadrado está completamente dentro de $C$ o completamente fuera de $C_{n+1}$, no tiene más interés y lo descartamos. De lo contrario, recurremos dividiendo el cuadrado. Si terminamos descartando todos los cuadrados, devolvemos 'verdadero'.

Este algoritmo puede resultar en una recursión infinita si el límite de $C$ y $C_{n+1}$ coinciden en algún punto. Sea un matemático aplicado y corte la recursión en una escala suficientemente pequeña, o sea un matemático puro y use alguna geometría algebraica para averiguar qué está sucediendo en la singularidad.

Answer 5

El problema (para discos de radios arbitrarios) es esencialmente equivalente a lo siguiente: dado un conjunto poliedral convexo en $\mathbb R^3$ (representado por un sistema de desigualdades lineales), determinar si interseca la esfera $x^2+y^2+z^2=1$. Para resolver esto, uno puede verificar si el conjunto es compacto y enumerar sus vértices para ver si se encuentra dentro de la esfera, y minimizar $x^2+y^2+z^2$ sobre el conjunto para averiguar si está completamente fuera. No soy un experto en complejidad pero creo que la primera se puede hacer en tiempo $O(n^2)$ y la segunda es aún más rápida.

La reducción se hace de la siguiente manera. Construye una proyección estereográfica desde el plano hacia la esfera de tal manera que el disco principal $C_{n+1}$ se mapee a la mitad superior. Cada otro disco se mapea a un casquete esférico que puede representarse como el conjunto solución de una desigualdad lineal (cuyos coeficientes son fáciles de calcular) intersecada con la esfera. Agrega la desigualdad $z \le 0$ para la mitad inferior. Ahora necesitamos averiguar si la unión de los semiespacios correspondientes cubren la esfera. O, equivalentemente, si la intersección de sus semiespacios complementarios tiene una intersección vacía con la esfera. Q.E.D.

El hecho de que los casquetes esféricos surjan de discos en el plano (es decir, no de complementos de discos) significa que los semiespacios complementarios excepto el último contienen el polo sur $(0,0,-1)$. Sin embargo, esto no ayuda mucho. Si los radios originales son iguales, entonces los semiespacios complementarios también contienen el centro $(0,0,0)$. Esto descarta el caso cuando la intersección está fuera de la esfera y, por lo tanto, simplifica un poco el problema.