1 Geometria obliczeniowa Wykład 3Podział wielokąta prostego na wielokąty monotoniczne. Podział wielokąta prostego na wielokąty wypukłe. Znajdowanie par przecinających się odcinków. Znajdowanie pary najbliższych punktów.

2 Podział wielokąta prostego na wielokąty monotoniczne.Do rozwiązania tego problemu wykorzy-stamy metodę zamiatania. Miotła będzie równoległa do osi x-ów. Definicje. Pomocnikiem krawędzi e wielokąta P nazy-wamy wierzchołek v, który jest prawym końcem równoległego do miotły odcinka łączącego v z e, leżącego powyżej miotły i najbliższego niej, którego wnętrze jest zawarte we wnętrzu P. Wielokąt nazywamy y-monotonicznym, gdy jest monotoniczny względem osi y-ów. v e v e

3 Wyróżniamy pięć rodzajów wierzchołków wielokąta w zależności od pozycji miotły przechodzącej przez dany wierzchołek (badamy wewnętrzne kąty wielokąta) : początkowy, gdy obie wychodzące z niego krawędzie leżą przed miotłą i tworzą kąt < , dzielący, gdy obie wychodzące z niego krawędzie leżą przed miotłą i tworzą kąt > , końcowy, gdy obie wychodzące z niego krawędzie leżą za miotłą i tworzą kąt < , łączący, gdy obie wychodzące z niego krawędzie leżą za miotłą i tworzą kąt > , prawidłowy, w pozostałych przypadkach.

4 Lemat. Wielokąt, który nie ma wierzchołków dzielących i łączących, jest y-monoto-niczny. Dowód. Załóżmy, że wielokąt nie jest y-mono-toniczny. Wtedy przecięcie poziomej prostej l z wielokątem tworzy co naj-mniej dwie spójne składowe. Istnieje odcinek na zewnątrz wielokąta łączący je. Weźmy ciąg krawędzi wielokąta łączących końce tego odcinka i nieprzecinający prostej. Najbardziej odległy od l wierzchołek takiej łamanej jest wierzchołkiem dzielącym lub łączącym. l l

5 Naszym zadaniem będzie dodanie prze-kątnych likwidujących wierzchołki łą-czące i dzielące.Strukturą zdarzeń będzie lista L uporząd-kowanych malejąco względem y-ów wierzchołków danego wielokąta P. Strukturą stanu będzie wzbogacone, zrównoważone drzewo poszukiwań binarnych T przechowujące w liściach ciąg aktualnie przecinanych przez miotłę krawędzi ograniczających wielokąt P z lewej strony wraz z dowiązaniami do ich pomocników.

6 W zależności od rodzaju wierzchołka v, który odwiedza miotła wykonywane są na-stępujące procedury. Niech el (ep) oznacza lewą (prawą) krawędź o końcu w wierz-chołku początkowym, końcowym, dzielącym lub łączącym. Niech ev oznacza krawędź le-żącą bezpośrednio na lewo od v. Wierzchołek początkowy . wstaw el do T; pomocnik(el) := v; Wierzchołek końcowy. if pomocnik(el) jest wierzchołkiem łączącym then wstaw przekątną miedzy v i pomocnik(el); usuń el z T; v v

7 Wierzchołek dzielący. znajdź w T krawędź ev ; wstaw przekątną między v i pomocnik(ev); pomocnik(ev) := v; wstaw ep do T i pomocnik(ep) := v; Wierzchołek łączący. if pomocnik(ep) jest wierzchołkiem łączącym then wstaw przekątną między v i pomocnik(ep); usuń ep z T; if pomocnik(ev) jest wierzchołkiem łączącym pomocnik(ev); v v

8 Wierzchołek prawidłowy.Niech eg (ed) będzie krawędzią powyżej (poniżej) v. if wnętrze P leży na prawo od v then if pomocnik(eg) jest wierzchołkiem łączącym then wstaw przekątną między v i pomocnik(eg); usuń eg z T; wstaw ed do T i pomocnik(ed) := v; else znajdź w T krawędź ev ; if pomocnik(ev) jest wierzchołkiem łączącym then wstaw przekątną między v i pomocnik(ev); pomocnik(ev) := v;

9 Algorytm podziału wielokąta P na wielokąty monotoniczne.L := {p1, p2, , pn}; T := puste ; while L   do v := FRONT(L); POP(L); wywołaj odpowiednią procedurę badającą v zależnie od jego rodzaju;

10 Lemat. Powyższy algorytm znajduje zbiór nie przecinających się przekątnych, które dzielą wielokąt prosty P na wielokąty monotoniczne. Dowód. Algorytm likwiduje wierzchołki łączące i dzielące, więc otrzymujemy podział na wielokąty monotoniczne. Z definicji pomocnika wynika, że w chwili dodawania przekątnej między miotłą a odcinkiem łączącym go z odpowiadającą mu krawędzią nie ma innych elementów. Zatem można go połączyć z aktualnie badanym wierzchołkiem przekątną nie przecinającą się z żadną inną.

11 Lemat. Prosty wielokąt o n wierzchołkach można powyższym algorytmem podzielić na y-monotoniczne wielokąty w czasie O(n log n) używając O(n) pamięci. Dowód. Sortowanie wierzchołków wymaga czasu O(n log n). Przetworzenie jednego wierzchołka wymaga czasu logarytmicznego, więc zamiatanie wykonujemy w czasie O(n log n). Wszystkie wykorzystywane struktury danych mają liniowy rozmiar. Twierdzenie (Chazelle). Dowolny wielokąt prosty można striangulować w czasie O(n).

12 Podział wielokąta prostego na wielokąty wypukłe.Lemat. Niech  oznacza minimalną liczbę wielokątów wypukłych, na które moż-na podzielić dany wielokąt odcinkami (niekoniecznie przekątnymi). Niech r będzie liczbą kątów wewnętrznych wielokąta o rozwartości większej niż . Wtedy:  r/2 + 1    r +1. Definicja. Dla danego podziału wielokąta przekątnymi istotną przekątną nazywamy taką, której usunięcie powoduje powstanie wielokąta mającego kąt wewnętrzny o rozwartości większej niż .

13 Fakt. Istotne przekątne nie są wyznaczone jednoznacznie. Lemat. Wierzchołek kąta wewnętrznego o rozwartości większej niż  jest koń-cem co najwyżej dwóch przekątnych istotnych. Dowód. Proste zawierające ramiona kąta wyznaczają dwie półpłaszczyzny. Do każdej z nich może należeć co najwyżej jedna przekątna istotna.

14 Algorytm Hertela i Mehlhorna.strianguluj wielokąt; usuń wszystkie przekątne, które nie są istotne; Nieistotne przekątne można wy-eliminować w czasie O(n) (w sta-łym czasie sprawdzamy, czy po usunięciu danej przekątnej, przy którymś z wierzchołków powstanie kąt większy od ) .

15 Twierdzenie. Liczba wielokątów wypukłych otrzymanych z pomocą algorytmu Hertela-Mehlhorna jest co najwyżej czterokrotnie większa niż minimalna liczba takich wielokątów. Dowód. Algorytm Hertela-Mehlhorna tworzy co najwyżej 2r+1 wielokątów. Na podstawie poprzednich lematów mamy: 2r+1  2r+4  4.

16 Znajdowanie par przecinających się odcinków.Problem: Dla zbioru n odcinków S znajdź wszystkie pary przecinających się odcinków z S. Problem przecinających się odcinków można łatwo rozwiązać w czasie O(n2). W tym celu wystarczy sprawdzić oddzielnie każdą parę odcinków. Takie rozwiązanie jest optymalne, gdy liczba par przecinających się odcinków jest kwadratowa. Chcemy znaleźć algorytm wrażliwy na wynik, tzn. algorytm, którego złożoność będzie zależeć od rozmiaru rozwiązania.

17 Metoda zamiatania. Miotła będzie zamiatać wzdłuż osi x-ów. W każdym położeniu miotły odcinkami przetworzonymi nazywamy wszystkie odcinki, których końce znajdują się na lewo od niej. Odcinkami aktywnymi są odcinki aktualnie przecinające miotłę. Do zbioru odcinków oczekujących należą odcinki o obu końcach na prawo od miotły. Będziemy korzystać z dwóch struktur danych. Struktura zdarzeń Q jest zrównoważonym drzewem poszukiwań binar-nych zawierającym uporządkowane rosnąco względem x-ów końce odcinków oraz punkty przecięć wszystkich par odcinków aktywnych, które kiedykolwiek były sąsiadami w strukturze. Struktura stanu T jest wzbogaconym, zrównoważonym drzewem poszu-kiwań przechowującym w liściach zbiór odcinków aktywnych uporządko-wanych względem współrzędnych y-owych.

18 Po dojściu miotły do kolejnego punktu zdarzenia mamy trzy możliwości.Zdarzenie jest początkiem odcinka s z S. wstaw s do T; uaktualnij dowiązania; if w jest sąsiadem s w T then if w przecina s w punkcie p then wstaw p do Q; Zdarzenie jest końcem odcinka s z S. usuń s z T; uaktualnij dowiązania; if s miał w T dwóch sąsiadów w, z then if w przecina z w punkcie p then wstaw p do Q, jeśli go tam jeszcze nie ma;

19 Zdarzenie jest punktem przecięcia odcinków s,z  S.Zamień kolejność s i z w T; if w jest sąsiadem s then if w przecina s w punkcie p then wstaw p do Q , jeśli go tam jeszcze nie ma; if v jest sąsiadem z then if v przecina z w punkcie q then wstaw q do Q , jeśli go tam Lemat. Jeśli punkt przecięcia dwóch odcin-ków leży po prawej stronie, najbliżej miotły, to znajduje się w strukturze Q.

20 Algorytm (Bentley-Ottmann).wstaw do Q końce odcinków z S; T := puste; while Q pusty do q := minimalny element w Q; usuń q z Q; wywołaj odpowiednią procedurę badającą q zależnie od jego rodzaju;

21 Twierdzenie. Algorytm znajduje wszystkie pary przecięć odcinków ze zbioru S w czasie O((n+k) log n), gdzie k jest liczbą przecięć. Dowód. Jeśli dwa odcinki przecinają się, to istnieje położenie miotły poprzedzające to przecięcie, w którym przecinające się odcinki sąsiadują w strukturze T. Zatem każdy punkt przecięcia jest znajdywany. Operacje wykonywane w dowolnym kroku algorytmu wymagają czasu logarytmicznego (stała liczba wstawień, usunięć, wyszukiwań elementów w zrównoważonym drzewie poszukiwań). Algorytm wykonuje 2n+k kroków. Zatem jego złożoność wynosi O((n+k) log n). Wniosek. Znalezienie odpowiedzi na pytanie, czy w zbiorze S istnieje para przecina-jących się odcinków wymaga czasu O(n log n). Istnieje algorytm (Balabana) znajdujący wszystkie przecięcia odcinków w czasie O(n log n + k) i pamięci O(n).

22 Znajdowanie pary najbliższych punktów.Problem: W zbiorze S zawierającym n punktów na płaszczyźnie znajdź parę wyznaczającą odcinek o najmniejszej długości. Problem ten można łatwo rozwiązać w czasie O(n2) badając wszystkie pary punktów. Wykorzystamy algorytm zamiatania w celu znalezienia rozwiązania problemu w czasie O(n log n).

23 Miotła poruszać się będzie wzdłuż osi x-ów.Punktami aktywnymi będziemy nazywać punkty z S znajdujące się w lewo-stronnie otwartym pasie X o szerokości równej najmniejszej odległości między dotychczas zamiecionymi punktami. Początkowo szerokość pasa jest nieskończona. Niech ix oznacza minimalny indeks punktu z X. Strukturą zdarzeń jest uporządkowana lista L punktów z S. Strukturą stanu będzie zrównoważone drzewo poszukiwań binarnych T przechowujące zbiór punktów aktywnych uporządkowanych względem współrzędnej y. Lemat. Punkty w pasie X można uporządkować względem współrzędnej y. Dowód. Ponieważ pas jest lewostronnie otwarty i ma szerokość równą najmniejszej odległości między dotychczas zamiecionymi punktami, więc żadne dwa punkty w pasie nie mogą mieć tej samej współrzędnej y-owej.

24 Algorytm. L := {p1, p2, , pn}; T := puste ; dmin:= +; ix:= 1; while L   do v := FRONT(L); POP(L); while d(ix,v)  dmin do T := T – {pix}; ix:= ix+1; znajdź w T punkty odległe od v wzglę-dem współrzędnej y o mniej niż dmin, wybierz bliższy z nich (w) i oblicz odległość d (d := + w p.p.); T := T  {v}; if d < dmin then dmin := d; C := {v, w};

25 Lemat. W każdym kroku algorytmu badamy co najwyżej 5 par punktów. Twierdzenie. Dla danego zbioru n punktów na płaszczyźnie najbliższą parę punktów możemy znaleźć w czasie O(n log n). Dowód. Dla każdego zdarzenia wykonujemy stałą liczbę operacji, z których każda kosztuje co najwyżej O(log n). Ponieważ zdarzeń jest n, więc złożoność algorytmu wynosi O(n log n).

26 Dziękuję za uwagę.

27 Ćwiczenia 3. 1. Udowodnij, że każdy wielokąt umożliwia triangulację, nawet jeśli ma dziury. Co można powiedzieć o liczbie trójkątów w triangulacji ? 2. Udowodnij lub zaprzecz: Graf dualny triangulacji wielokąta monotonicznego jest zawsze łańcuchem, tzn. każdy węzeł tego grafu ma stopień 2. 3. Podaj algorytm, który w czasie O(n log n) oblicza przekątną dzielącą prosty wielokąt o n wierzchołkach na dwa wielokąty z co najwyżej 2n/3 +2 wierzchołkami w każdym z nich. 4. Niech P będzie prostym wielokątem o n wierzchołkach, który podzielono na monotoniczne części. Udowodnij, że suma liczby wierzchołków tych części jest O(n).

28 5. Niech S będzie zbiorem n trójkątów na płaszczyźnie5. Niech S będzie zbiorem n trójkątów na płaszczyźnie. Brzegi trójkątów są rozłączne, ale jest możliwe, że trójkąt leży całkowicie wewnątrz drugiego trójkąta. Niech P będzie zbiorem n punktów na płaszczyźnie. Podaj algorytm działający w czasie O(n log n), który znajduje punkty leżące poza trójkątami. 6. Niech S będzie zbiorem n rozłącznych trójkątów na płaszczyźnie. Chcemy znaleźć zbiór n-1 odcinków o następujących własnościach: - każdy odcinek łączy punkty brzegowe dwóch trójkątów, - wnętrza odcinków są parami rozłączne i są one rozłączne z trójkątami, - Ciągi odcinków łączą wszystkie trójkąty każdy z każdym, tzn. z każdego trójkąta można dojść do dowolnego innego. Stwórz algorytm działający w czasie O(n log n). 7. Mając dany ciąg kolejnych krawędzi wielokąta prostego oblicz w czasie liniowym jego pole.

29 8. Niech  oznacza minimalną liczbę wielokątów wypukłych, na które można podzielić dany wielokąt (niekoniecznie przekątnymi). Niech r będzie liczbą kątów wewnętrznych wielokąta o rozwartości większej niż . Wtedy:  r/2 + 1    r Niech S będzie zbiorem n okręgów na płaszczyźnie. Opisz algorytm zamiatania obliczający wszystkie punkty przecięć okręgów. (okręgi mogą zawierać się jeden w drugim) 10. W każdym kroku algorytmu znajdowania najbliższej pary punktów badamy co najwyżej 5 par punktów.