Pokrycie prostokąta przez linię przeciągnięcia

Dostałem ćwiczenie, niestety nie udało mi się.

Istnieje zestaw prostokątów i prostokąt . Za pomocą algorytmu zamiatania płaszczyzny ustal, czy jest całkowicie objęte zestawem .$R_{1}..R_{n}$$R_{0}$$R_{0}$$R_{1}..R_{n}$

Więcej informacji na temat zasady algorytmów linii przeciągnięcia znajduje się tutaj .

Zacznijmy od początku. Początkowo znamy algorytm linii przeciągnięcia jako algorytm znajdowania skrzyżowań segmentów linii, który wymaga dwóch struktur danych:

• zestaw punktów zdarzeń (przechowuje punkty końcowe segmentów i punkty przecięcia)$Q$
• status (struktura dynamiczna dla zestawu segmentów przecinających się linii przeciągnięcia)$T$

Ogólna idea: załóż, że linia przeciągnięcia jest linią pionową, która zaczyna zbliżać się do zestawu prostokątów od lewej. Posortuj wszystkie współrzędne prostokątów i zapisz je w kolejności w kolejności rosnącej - powinno przyjąć . Zacznij od pierwszego punktu zdarzenia, dla każdego punktu określ zbiór prostokątów przecinających się przy danej współrzędnej , zidentyfikuj ciągłe segmenty prostokątów przecięcia i sprawdź, czy pokrywają całkowicie przy bieżącej współrzędnej . Z jako drzewem binarnym zajmie . Jeśli jakakolwiek część pozostaje odkryta, to$l$$x$$Q$$O(n\log n)$$x$$R_{0}$$x$$T$$O(\log n)$$R_{0}$$R_{0}$ nie jest całkowicie uwzględniony.

Szczegóły: Idea algorytmu przecięcia segmentu była taka, że ​​przecinają się tylko sąsiednie segmenty. Na podstawie tego faktu zbudowaliśmy status i utrzymaliśmy go w całym algorytmie. Próbowałem znaleźć podobny pomysł w tym przypadku i jak dotąd bez powodzenia, jedyne co mogę powiedzieć, to dwa prostokąty przecinają jeśli odpowiadające im i współrzędne pokrywają się.$T$$x$$y$

Problem polega na tym, jak zbudować i utrzymać , a co złożoność budowy i utrzymania jest. Zakładam, że drzewa R mogą być bardzo przydatne w tym przypadku, ale ponieważ stwierdziłem, że bardzo trudno jest określić minimalny prostokąt ograniczający za pomocą drzew R.$T$$T$

Czy masz pojęcie o tym, jak rozwiązać ten problem, a zwłaszcza jak zbudować ?$T$

Zacznijmy od prostokątów wyrównanych do osi , ponieważ istnieje rodzaj łatwego bezpośredniego argumentu. Zamiatamy pionową linię. Zdarzenia są punktami końcowymi poziomych krawędzi prostokątów. Podczas omiatania utrzymujemy zestaw interwałów na linii zamiatania, które są „odkryte” przez , :$n$$R_i$$i\ge 1$

• Dodaj pionowy interwał objęty prostokątem do linii przeciągnięcia, gdy po raz pierwszy napotkamy$R_i$$R_i$
• Usuń odstęp pionowy objęty prostokątem z linii przeciągnięcia, gdy przesuwa się on poza$R_i$$R_i$

Można to łatwo zrobić za pomocą drzewa binarnego, aby aktualizacje zajmowały czas . (Problem jest zasadniczo jednowymiarowy. Dowiesz się, czy punkty końcowe znajdują się w nieosłoniętym przedziale i odpowiednio przedłużasz / scalasz podczas dodawania i wydłużasz je podczas usuwania.)$O(\log n)$

Następnie sprawdzasz tylko, czy w zakresie żaden z odsłoniętych przedziałów nigdy nie przecina pionowego zakresu . Cała rzecz to czas przestrzeń .$R_0$$R_0$$O(n\log n)$$O(n)$

W ogólnym przypadku oczywista sztuczka nie jest tak szybka. Użyj standardowego algorytmu linii przeciągnięcia, aby obliczyć cały podział planarny wywołany przez prostokąty.

Najwyraźniej jakiś podobny do dysku zestaw ścian obejmuje . Samo to nie mówi nam wystarczająco dużo, ponieważ interesuje nas to, czy którakolwiek z tych ścian znajduje się wewnątrz i poza innymi prostokątami. Aby to zrobić, modyfikujemy nieco konstrukcję, aby po dodaniu krawędzi oznaczyć jedną stronę identyfikacją prostokąta, który jest w środku. Dodaje to narzut , więc konstrukcja ma czas ; bez założeń dotyczących prostokątów, wyjście może mieć wielkość , więc w najgorszym przypadku używamy tyle miejsca, więc czas jest „optymalny egzystencjalnie”, choć nie „wrażliwy na wyjście”.$F'$$R_0$$R_0$$O(1)$$O(n^2\log n)$$\Omega(n^2)$

Wreszcie, jest zakryty, o ile żadna z powierzchni w ma tylko krawędzi jako znajdujące się w jednym z . Chodzi o to, że jeśli krawędź znajduje się w , to cała również również. Wyobraźmy sobie, zamiatanie linię nad prostopadle wzdłuż tej krawędzi: może tylko zostawić albo poza lub jest ograniczona przez więcej niż jednej krawędzi .$R_0$$F'$$R_i$$f$$R_i$$f$$f$$R_i$$f$$f$$R_i$

Wniosek jest taki, że szczególny przypadek to a ogólny to co najmniej , ale podejrzewam, że można to poprawić.$O(n\log n)$$O(n^2\log n)$