Si un punto se encuentra en todos los círculos

Question

Tengo un set de n dado círculos. Quiero saber que si existe al menos un punto que se encuentra en todos los de los círculos. Existe algún método para hacerlo? Definitivamente puedo encontrar un conjunto de puntos y luego iterar sobre ellos, pero todo lo que quiero es saber si existe la posibilidad, no tengo ningún uso de el punto exacto(s).

PS: los Círculos pueden ser de cualquier radios

Answer 1

Descaradamente apuntalamiento de mi respuesta anterior:

Lo que usted está preguntando es si la intersección de $n$ discos es no vacío. Dijo que la intersección es una convexidad delimitado por arcos circulares que se encuentran en los vértices donde dos o más círculos se intersectan.

Considerar cada par de círculos; a encontrar su dos puntos de intersección, que forman dos candidatos vértices; si un candidato vértice está en el interior de todos los demás círculos, entonces se trata de un vértice de la intersección. Esto le da al conjunto de vértices de la intersección de la forma.

Entonces, la intersección es no vacío si y sólo si: (i) el conjunto de vértices es no vacío, o (ii) existe un círculo que está completamente dentro de todos los demás.

---

Como Hagen von Eitzen, el no-muy-inteligente algoritmo se $O(n^3)$ del tiempo. Una manera mucho más eficiente de la solución es posible.

En lugar de encontrar a cualquier punto en la intersección de los discos, vamos a tratar de encontrar la izquierda del punto, es decir, el punto con la menor $x$-coordinar. Específicamente, para cualquier conjunto de discos de $S$, definir $f(S)$ a ser el más pequeño $x$-coordenadas de todos los puntos de la intersección $\bigcap S$ o $+\infty$ si $\bigcap S$ está vacía.

Computación $f$ es un LP-tipo de problema debido a $f$ satisface las siguientes dos propiedades:

1. Monotonía: si $A\subseteq B$$f(A)\le f(B)$. Esto es debido a la adición de más discos sólo pueden reducir la intersección y hacer que los más pequeños $x$-coordinar más grande. Formalmente, $\bigcap B\subseteq\bigcap A$.

2. Localidad: si $A\subseteq B$$f(A)=f(B)=f(A\cup\{x\})$,$f(A)=f(B\cup\{x\})$. Esto es debido a que la primera igualdad implica que el punto más a la izquierda en $\bigcap A$ se encuentra en $\bigcap B$ y en $x$, y así también se encuentra en $\bigcap\big(B\cup\{x\}\big)$.

Siendo un LP-tipo de problema, $f$ puede ser calculado en espera $O(n)$ tiempo por cualquiera de varios algoritmos aleatorizados.

Ver la analogía con la programación lineal, supongo que este algoritmo es como el método simplex, mientras que la anterior es como encontrar todos los posibles vértices de la factible polytope y prueba de los mismos.