Cobertura retangular por linha de varredura

Fiz um exercício, infelizmente, não consegui sozinho.

Há um conjunto de retângulos e um retângulo . Usando o algoritmo de varredura de avião, determine se é completamente coberto pelo conjunto de .$R_{1}..R_{n}$$R_{0}$$R_{0}$$R_{1}..R_{n}$

Para mais detalhes sobre o princípio dos algoritmos de linha de varredura, consulte aqui .

Vamos começar do começo. Inicialmente, conhecemos o algoritmo de linha de varredura como o algoritmo para encontrar interseções de segmentos de linha, o que requer duas estruturas de dados:

• um definido de pontos de evento (armazena pontos finais de segmentos e pontos de interseção)$Q$
• um status $T$ (estrutura dinâmica para o conjunto de segmentos que a linha de varredura cruza)

A idéia geral: suponha que a linha de varredura $l$ é uma linha vertical que começa a se aproximar do conjunto de retângulos da esquerda. Classifique todas as coordenadas $x$ dos retângulos e armazene-as em $Q$ em ordem crescente - deve usar $O(n\log n)$ . Comece do primeiro ponto do evento, para cada ponto determine o conjunto de retângulos que se cruzam na coordenada x especificada $x$, identifique segmentos contínuos dos retângulos de interseção e verifique se eles cobrem $R_{0}$ completamente na coordenada x atual $x$. Com $T$ como uma árvore binária, será necessário $O(\log n)$ . Se alguma parte de $R_{0}$ permanecer descoberta, essa$R_{0}$ não é completamente coberto.

Detalhes: a ideia do algoritmo de interseção de segmentos era que apenas segmentos adjacentes se cruzam. Com base nesse fato, criamos o status $T$ e o mantemos durante todo o algoritmo. Tentei encontrar uma idéia semelhante nesse caso e, até agora, sem sucesso, a única coisa que posso dizer é que dois retângulos se cruzam se as coordenadas correspondentes $x$ e $y$ sobrepõem.

O problema é como construir e manter $T$ , e que a complexidade de construir e manter $T$ é. Suponho que as árvores R possam ser muito úteis nesse caso, mas como eu achei muito difícil determinar o retângulo delimitador mínimo usando árvores R.

Você tem alguma idéia de como resolver esse problema e, particularmente, de como construir o ?$T$

Vamos começar com retângulos alinhados ao eixo, pois existe um tipo de argumento direto fácil. Vamos varrer uma linha vertical. Os eventos são os pontos finais das arestas horizontais dos retângulos. À medida que varremos, mantemos um conjunto de intervalos na linha de varredura que são "descobertos" por R i , i ≥ 1 :$n$$R_i$$i\ge 1$

• Adicione o intervalo vertical coberto pelo retângulo à linha de varredura quando encontrarmos R i pela primeira vez$R_i$$R_i$
• Remova o intervalo vertical coberto pelo retângulo da linha de varredura quando passar por R $R_i$$R_i$

É fácil fazer isso com uma árvore binária, para que as atualizações levem tempo . (O problema é essencialmente unidimensional. Você descobre se os pontos de extremidade estão em um intervalo descoberto e os estende / mescla adequadamente ao adicioná-los e aumenta-os ao removê-los.)$O(\log n)$

Depois, verifique se, no intervalo de , nenhum dos intervalos descobertos cruza o intervalo vertical de R 0 . A coisa toda é tempo O ( n log n ) e espaço O ( n ) .$R_0$$R_0$$O(n\log n)$$O(n)$

Para o caso geral, o truque óbvio não é tão rápido. Use o algoritmo de linha de varredura padrão para calcular toda a subdivisão planar induzida pelos retângulos.

Claramente, um conjunto tipo disco das faces cobre R 0 . Por si só, isso não nos diz o suficiente, pois estamos interessados ​​em saber se alguma dessas faces está dentro de R 0 e fora dos outros retângulos. Para fazer isso, modificamos um pouco a construção, de modo que, quando adicionamos uma aresta, identificamos um lado com a identidade do retângulo que está dentro. Isso adiciona O ( 1 ) à sobrecarga, portanto a construção é O ( n 2 log n ) ; sem suposições sobre os retângulos, a saída pode ser Ω ( n 2$F'$$R_0$$R_0$$O(1)$$O(n^2\log n)$$\Omega(n^2)$ em tamanho, então estamos usando tanto espaço no pior dos casos; portanto, o tempo é "existencialmente ideal", embora não seja "sensível à saída".

Finalmente, é coberto desde que nenhuma das faces em F ' tenha apenas arestas não marcadas como estando em um dos R i . A questão é que se uma aresta de f é em R i , em seguida, o conjunto de F é tão bem. Imaginar varrer uma linha ao longo do f ortogonalmente ao longo desta borda: ela só pode sair R i , quer fora de f ou f é delimitada por mais do que uma borda de R i .$R_0$$F'$$R_i$$f$$R_i$$f$$f$$R_i$$f$$f$$R_i$

Portanto, a conclusão é que o caso especial é e o geral é O ( n 2 log n ) pelo menos, mas suspeito que possa ser melhorado.$O(n\log n)$$O(n^2\log n)$