Algoritmo para determinar si un conjunto de discos de la unidad cubre el disco unidad de centrado en el origen?

Question

Tengo una lista de puntos de $ (x_i, y_i) $$i = 1...n$. Existe un algoritmo para determinar si la unión de la unidad de discos centra en estos puntos es un superconjunto de la unidad de disco centrado en $(0, 0)$?

De manera informal, estoy a punto de hacer un montón de no-transparente llena de círculos y quiero saber si realmente me moleste en hacer un dibujo de todos ellos. Algunos de ellos pueden ser cubiertos por los círculos que voy a dibujar más tarde. Todos los círculos son del mismo tamaño para que yo pueda hacer algo simple de preprocesamiento para darles a todos los radio 1 y puedo moverlos de manera que el círculo que yo no necesite dibujar es de a $(0, 0)$.

Para decirlo de una manera diferente, tengo una lista de desigualdades cuadráticas de la forma: $$ \begin{aligned} x^2 + y^2 \leq 1 \\ (x - x_1)^2 + (y - y_1)^2 \geq 1 \\ (x - x_2)^2 + (y - y_2)^2 \geq 1 \\ (x - x_3)^2 + (y - y_3)^2 \geq 1 \\ ... \end{aligned} $$ y la necesidad de determinar si hay un punto que satisface todos ellos.

Answer 1

Deje$p_i = (x_i, y_i)$, con$p_0 = (0,0)$. Para cada$i$ y$j$ con$0 \le i < j \le n$, examinar la (como máximo 2) señala$q$ con$|p_i - q| = |p_j - q| = 1$. Con el fin de$q$ para ser un punto de la región$\{p: |p - p_0| \le 1, |p - p_i| > 1\ {\rm for}\ i \ge 1\}$ frontera, necesitamos$|q - p_0| \le 1$,$|q - p_k| \ge 1$ para todos los$k \ge 1$, y tiene que haber un vector no nulo $v$% tal que $(q - p_i) . v \ge 0$para todos los$i> 0$ para los que$|q - p_i| = 1$, mientras que$(q - p_0) . v < 0$ if$|q - p_0| = 1$. La programación lineal se puede usar para decidir si existe un vector tal.

Answer 2

El siguiente algoritmo funciona, aunque puede ser un poco más complicado de lo que usted está buscando:

1. Calcular el diagrama de Voronoi correspondientes a los puntos de $(x_i,y_i)$. Hay un conocido algoritmo que se ejecuta en $n \log n$ del tiempo. Ver el artículo de Wikipedia sobre triangulaciones de Delaunay.

2. Deje $S$ el conjunto de vértices del diagrama de Voronoi, que se encuentran en el disco de $x^2 + y^2 \leq 1$, y deje $S'$ sea el conjunto de puntos en el círculo de $x^2+y^2=1$ que se encuentran en el borde del diagrama de Voronoi.

3. A continuación, el dado de los discos de la cubierta del disco $x^2+ y^2 \leq 1$ si y sólo si el dado discos de cubrir los puntos en $S\cup S'$.

Answer 3

Supongamos que la unidad de discos ("dado de discos") cruzan la unidad de disco en el origen ("origen de disco"), pero no lo cubra por completo (se puede ignorar dado los discos que no se intersecan en el origen de disco). Por lo tanto, debe haber un punto en el origen de disco que está en la frontera de un determinado disco, pero no cubiertos por el interior de cualquier otro disco (prueba: recogida descubierta, punto, y considerar el más cercano disco dado). Esto reduce nuestro objetivo a la comprobación, por cada disco de $D$, si todos los puntos de la intersección $B$ de su límite con el origen de disco están cubiertos por algún disco dado.

Para cualquier disco de $D' \neq D$, se puede calcular la intersección de $B$ $D'$ ya que a través de la informática de varias intersecciones de $D$, $D'$ y el origen de disco. Además, se puede parametrizar $B$ como un intervalo de $[0,1]$, y el presente $B \cap D'$ cerrado subinterval de $[0,1]$.

La pregunta es, por tanto, reducida a determinar si algunos de los subintervalos de $[0,1]$ de cobertura. Ordenar los intervalos y la verificación de que los intervalos adyacentes se superponen, y que ambos extremos están cubiertos (no he flasheado los detalles, pero, probablemente, un algoritmo puede ser construido a lo largo de estas líneas).

La aplicación de este método de manera eficiente puede ser complicado, y no creo que en la práctica se ahorrará el tiempo de esta manera.