Couverture rectangulaire par ligne de balayage

On me fait un exercice malheureusement je n'ai pas réussi par moi-même.

Il y a un ensemble de rectangles et un rectangle . En utilisant un algorithme de balayage plan, déterminez si est complètement couvert par l'ensemble de .$R_{1}..R_{n}$$R_{0}$$R_{0}$$R_{1}..R_{n}$

Pour plus de détails sur le principe des algorithmes de ligne de balayage, voir ici .

Commençons depuis le début. Initialement, nous connaissons l'algorithme de ligne de balayage comme l'algorithme de recherche d' intersections de segments de ligne qui nécessite deux structures de données:

• un ensemble de points d'événement (il stocke les extrémités des segments et des points d'intersections)$Q$
• un état (structure dynamique pour l'ensemble des segments coupés par la ligne de balayage)$T$

L'idée générale: supposons que la ligne de balayage est une ligne verticale qui commence à se rapprocher de l'ensemble de rectangles à partir de la gauche. Trier toutes les coordonnées des rectangles et les stocker dans dans l'ordre croissant - devrait prendre . Commencez par le premier point d'événement, pour chaque point, déterminez l'ensemble de rectangles qui se croisent à la coordonnée donnée , identifiez les segments continus des rectangles d'intersection et vérifiez s'ils couvrent complètement à la coordonnée actuelle . Avec comme arbre binaire, ça va prendre . Si une partie de reste découverte,$l$$x$$Q$$O(n\log n)$$x$$R_{0}$$x$$T$$O(\log n)$$R_{0}$$R_{0}$ n'est pas complètement couvert.

Détails: L'idée de l'algorithme d'intersection de segments était que seuls les segments adjacents se croisent. Sur la base de ce fait, nous avons construit l'état et l' avons maintenu tout au long de l'algorithme. J'ai essayé de trouver une idée similaire dans ce cas et jusqu'à présent sans succès, la seule chose que je peux dire est que deux rectangles se croisent si leurs coordonnées et y correspondantes se chevauchent.$T$$x$$y$

Le problème est de savoir comment construire et entretenir $T$ , et ce que la complexité de la construction et de maintenir $T$ est. Je suppose que les arbres R peuvent être très utiles dans ce cas, mais comme je l'ai trouvé, il est très difficile de déterminer le rectangle de délimitation minimum à l'aide des arbres R.

Avez-vous une idée de la façon de résoudre ce problème, et en particulier de la façon de construire ?$T$

Commençons par rectangles alignés sur l'axe, car il existe une sorte d'argument direct facile. Nous allons balayer une ligne verticale. Les événements sont les extrémités des bords horizontaux des rectangles. Pendant que nous balayons, nous maintenons un ensemble d'intervalles sur la ligne de balayage qui sont "découverts" par R i , i ≥ 1 :$n$$R_i$$i\ge 1$

• Ajouter l'intervalle vertical couvert par le rectangle à la ligne de balayage lors de la première rencontre avec R $R_i$$R_i$
• Supprimez l'intervalle vertical couvert par le rectangle de la ligne de balayage lorsqu'il passe devant R $R_i$$R_i$

Il est facile de le faire avec un arbre binaire afin que les mises à jour prennent du temps . (Le problème est essentiellement unidimensionnel. Vous déterminez si les points de terminaison sont dans un intervalle découvert et vous étendez / fusionnez de manière appropriée lors de leur ajout et vous les rallongez lors de leur suppression.)$O(\log n)$

Ensuite, vous vérifiez simplement que, dans la plage de , aucun des intervalles non recoupés n'a jamais recoupé la plage verticale de R 0 . Le tout est O ( n log n ) fois un espace O ( n ) .$R_0$$R_0$$O(n\log n)$$O(n)$

Pour le cas général, l'astuce évidente n'est pas aussi rapide. Utilisez l'algorithme de ligne de balayage standard pour calculer la subdivision plane entière induite par les rectangles.

Il est clair qu'un ensemble en forme de disque des faces couvre R 0 . En soi, cela ne nous en dit pas assez, car ce qui nous intéresse, c'est si l'une de ces faces est à l'intérieur de R 0 et à l'extérieur des autres rectangles. Pour ce faire, nous modifions un peu la construction, de sorte que lorsque nous ajoutons un bord, nous marquons un côté avec l'identité du rectangle à l'intérieur. Cela ajoute un surdébit O ( 1 ) , donc la construction est en temps O ( n 2 log n ) ; sans hypothèses sur les rectangles, la sortie peut être Ω ( n 2$F'$$R_0$$R_0$$O(1)$$O(n^2\log n)$$\Omega(n^2)$ en taille, donc nous utilisons autant d'espace dans le pire des cas, donc le temps est "existentiellement optimal" mais pas "sensible à la sortie".

Enfin, est recouvert tant qu'aucune des faces de F ' n'a que des arêtes non marquées comme étant dans l'une des R i . Le fait est que si une arête de f est dans R i , alors l'ensemble de f l' est aussi. Imaginez que vous balayez une ligne sur f orthogonalement le long de ce bord: il ne peut laisser R i qu'en dehors de f ou f est délimité par plus d'un bord de R i .$R_0$$F'$$R_i$$f$$R_i$$f$$f$$R_i$$f$$f$$R_i$

Donc, la conclusion est que le cas spécial est et le général est O ( n 2 log n ) au moins, mais je pense qu'il peut être amélioré.$O(n\log n)$$O(n^2\log n)$