Cobertura de rectángulo por línea de barrido

Me dan un ejercicio que desafortunadamente no tuve éxito por mí mismo.

Hay un conjunto de rectángulos y un rectángulo . Usando el algoritmo de barrido plano, determine si está completamente cubierto por el conjunto de .$R_{1}..R_{n}$$R_{0}$$R_{0}$$R_{1}..R_{n}$

Para obtener más detalles sobre el principio de los algoritmos de línea de barrido, consulte aquí .

Vamos a empezar desde el principio. Inicialmente, conocemos el algoritmo de línea de barrido como el algoritmo para encontrar intersecciones de segmento de línea que requiere dos estructuras de datos:

• un conjunto de puntos de evento (almacena puntos finales de segmentos y puntos de intersección)$Q$
• un estado (estructura dinámica para el conjunto de segmentos que cruzan la línea de barrido)$T$

La idea general: suponga que la línea de barrido es una línea vertical que comienza a acercarse al conjunto de rectángulos desde la izquierda. Ordene todas las coordenadas de los rectángulos y guárdelas en en orden creciente; debe tomar . Comience desde el primer punto de evento, para cada punto determine el conjunto de rectángulos que se cruzan en la coordenada dada , identifique segmentos continuos de rectángulos de intersección y verifique si cubren completamente en la coordenada actual . Con como árbol binario, tomará . Si alguna parte de permanece descubierta,$l$$x$$Q$$O(n\log n)$$x$$R_{0}$$x$$T$$O(\log n)$$R_{0}$$R_{0}$ no está completamente cubierto.

Detalles: La idea del algoritmo de intersección de segmentos era que solo los segmentos adyacentes se cruzan. En base a este hecho, creamos el estado y lo mantuvimos en todo el algoritmo. Traté de encontrar una idea similar en este caso y hasta ahora sin éxito, lo único que puedo decir es que dos rectángulos se cruzan si sus correspondientes coordenadas e superponen.$T$$x$$y$

El problema es cómo construir y mantener , y lo que la complejidad de construir y mantener es. Supongo que los árboles R pueden ser muy útiles en este caso, pero como encontré es muy difícil determinar el rectángulo límite mínimo usando árboles R.$T$$T$

¿Tienes alguna idea sobre cómo resolver este problema, y ​​particularmente cómo construir ?$T$

Comencemos con rectángulos alineados a los ejes, ya que hay una especie de argumento directo fácil. Barreremos una línea vertical. Los eventos son los puntos finales de los bordes horizontales de los rectángulos. A medida que barremos, mantenemos un conjunto de intervalos en la línea de barrido que están "descubiertos" por , :$n$$R_i$$i\ge 1$

• Agregue el intervalo vertical cubierto por el rectángulo a la línea de barrido cuando encontremos por primera vez$R_i$$R_i$
• Elimine el intervalo vertical cubierto por el rectángulo de la línea de barrido cuando pase$R_i$$R_i$

Es fácil hacer esto con un árbol binario para que las actualizaciones tomen tiempo . (El problema es, esencialmente, unidimensional. Usted descubre si los puntos finales están en un intervalo descubierto y los extiende / fusiona adecuadamente al agregarlos y los alarga al eliminarlos).$O(\log n)$

Luego simplemente verifica que, en el lapso de , ninguno de los intervalos descubiertos se cruza con el tramo vertical de . Todo el asunto es tiempo un espacio .$R_0$$R_0$$O(n\log n)$$O(n)$

Para el caso general, el truco obvio no es tan rápido. Use el algoritmo de línea de barrido estándar para calcular la subdivisión plana completa inducida por los rectángulos.

Claramente, un conjunto de discos de las caras cubre . Por sí solo, esto no nos dice lo suficiente, ya que lo que nos interesa es si alguna de estas caras está dentro de y fuera de los otros rectángulos. Para hacer esto, modificamos un poco la construcción, de modo que cuando agregamos un borde, etiquetamos un lado con la identidad del rectángulo que está dentro. Esto agrega sobrecarga, por lo que la construcción es tiempo; sin suposiciones en los rectángulos, la salida puede ser de tamaño , por lo que estamos usando ese espacio en el peor de los casos, por lo que el tiempo es "existencialmente óptimo" aunque no "sensible a la salida".$F'$$R_0$$R_0$$O(1)$$O(n^2\log n)$$\Omega(n^2)$

Finalmente, está cubierto siempre que ninguna de las caras en tenga solo bordes no etiquetados como si estuvieran en uno de los . El punto es que si un borde de está en , entonces la totalidad de está. Imagine barrer una línea sobre ortogonalmente a lo largo de este borde: solo puede dejar fuera de o está delimitado por más de un borde de .F ′ R i f R i f f R i f f R $R_0$$F'$$R_i$$f$$R_i$$f$$f$$R_i$$f$$f$$R_i$

Entonces, la conclusión es que el caso especial es y el general es al menos, pero sospecho que se puede mejorar.O ( n 2 log n $O(n\log n)$$O(n^2\log n)$