Wartownicy

Sezon urlopowy w pełni, warunki pogodowe (przynajmniej u mnie) dość ekstremalne, w ramach wakacyjnego relaksu proponuję więc dwa niezbyt trudne (ale przyjemne) zadania z ekstremalnej teorii grafów: pierwsze o pięciokątach, a drugie o kwadratach. Mniej więcej.

Pierwsze zadanie jest tak praktyczne, jak to tylko możliwe. Z n\leq 5000 punktów na płaszczyźnie chcemy wybrać 5 tak, aby utworzyć pięciokąt wypukły. W dodatku autor miał chyba dobry dzień, bo obiecał w treści, że żadne trzy z podanych punktów nie leżą na tej samej prostej. Zacznijmy od najbardziej brutalnego z możliwych rozwiązań, które przegląda wszystkie możliwe piątki punktów w czasie \mathcal{O}(n^5). Jest to, oczywiście, strasznie wolne. Może dałoby się choć trochę szybciej?

Pewnie by się dało. Powiedzmy, że ustaliliśmy 4 kolejne wierzchołki A,B,C,D naszego wymarzonego pięciokąta. Czy dałoby się jakoś sprytnie sprawdzić, czy można dołożyć do nich jeszcze jeden punkt tak, aby domknąć wielokąt? Lub, patrząc na sytuację trochę inaczej, czy dałoby się szybko sprawdzić niepustość zielonego obszaru?

pieciokat1

Pomyślmy o wypukłej otoczce wszystkich punktów. Jeśli A i D są na niej sąsiadami, zielony obszar nie może zawierać w środku żadnego punktu. Jeśli zaś nie są sąsiadami, możemy wybrać E będący jakimkolwiek punktem na otoczce (ściśle) pomiędzy A i D. Chwili zastanowienia wymaga jedynie sprawdzenie, że dla tak wybranego E kąty BAE i CDE są wypukłe. Jest tak dlatego, że wypułe są kąty A'AE i D'DE, gdzie A' jest poprzednikiem A, a D' następnikiem D na otoczce. Też na otoczce.

pieciokat2

Sprawdzenie, czy krawędź AD leżyna otoczce, może być wykonane w czasie stałym, więc udało nam się zmniejszyć złożoność do \mathcal{O}(n^4). Co przy n=5000 jest, niestety, całkowicie bezużyteczne. Ewidentnie potrzebny jest jakiś nowy pomysł.

W tym momencie warto spróbować narysować zbiór punktów, dla którego skonstruowanie pięciokąta wypukłego nie jest możliwe. Okazuje się (co jest, chyba, dość zaskakujące), że o ile możliwe jest skonstruowanie takiego zbioru ośmiu punktów, z każdego zbioru dziewięciu punktów da się wybrać pięć, które tworzą wielokąt wypukły! Czyli, tak naprawdę, można odrzucić wszystkie punkty poza dziewięcioma pierwszymi, a następnie skorzystać z opisanej wyżej metody, nawet bez wspomnianej optymalizacji, co daje nam rozwiązanie zadania. Ale właściwie dlaczego wystarcza dziewięć punktów?

Okazuje się, że prawdziwe jest nawet dużo silniejsze twierdzenie: dla każdego k istnieje liczba N(k) taka, że w dowolnym zbiorze N(k) punktów w położeniu ogólnym na płaszczyźnie (w położeniu ogólnym oznacza tylko tyle, że żadne trzy nie leżą na tej samej prostej) można znaleźć k-kąt wypukły. Jest to tak zwany Happy Ending problem, a właściwie jego uogólnienie rozważane przez Erdősa i Szekeresa. W miarę przystępny dowód tej ogólnej wersji można znaleźć w ich oryignalnej pracy, ale może popatrzmy na możliwy nietrywialny przypadek k=4, co pewnie choć trochę pomoże w uwierzeniu w prawdziwość tej silniejszej wersji.

Lemat. Dla każdego zbioru 5 punktów w położeniu ogólnym na płaszczyźnie można wybrać 4, które tworzą czworokąt wypukły.

Dowód. Popatrzmy na otoczkę wypukłą danego zbioru punktów. Jeśli są na niej przynajmniej 4 punkty, lemat jest prawdziwy. Załóżmy więc, że są tam tylko trzy punkty, czyli mam trójĸąt ABC z dwoma punktami DE w środku.

czworokat1

Teraz twierdzimy, że jeden z czworokątów utworzony przez D,E i dwa z punktów A,B,C na pewno jest wypukły. Weźmy bowiem prostą przechodzącą przez DE. Skoro trójkąt ma trzy wierzchołki, dwa z nich leżą po tej samej stronie tej prostej.

czworokat1

Teraz wystarczy tylko wybrać jako wierzchołki czworokąta właśnie D, E i te dwa z A,B,C, które leżą po tej samej stronie prostej.

Drugie zadanie pochodzi z jednej z ostatnich rund Codeforces. Jest, dla odmiany, o tablicy n\times m, w którym chcemy wybrać pola (i_1,j_1), (i_1,j_2), (i_2,j_1), (i_2,j_2) tak, aby zmaksymalizować najmniejszą ze znajdujących się w nich liczb. W dodatku chcemy je wybrać dość szybko, bo n,m\leq 1000, choć nie do końca wiadomo w jaką złożoność należy celować. O(n^2\log n)? O(n^3) z bardzo małą stałą? A może…

A może w rozwiązanie liniowe! Zacznijmy jednak od O(n^2\log n) (dla uproszczenia rachunków będziemy zakładać, że n=m). Powiedzmy, że chcemy sprawdzić, czy możliwe jest osiągnięcie minimum równego X lub więcej. Jak się do tego zabrać? Pewnie można skonstruować nową tablicę n\times m, w którym w polu (i,j) zapisujemy 1 lub 0 w zależności od tego, czy odpowiadające mu pole w oryginalnej tablicy zawierało X lub nawet większą liczbę. No i wiadomo czego powinniśmy szukać w tej nowej tablicy, ale trochę wygodniej jest zamiast o tablicy myśleć o grafie dwudzielnym. Graf ten ma n wierzchołków u_i odpowiadających kolumnom i m wierzchołków v_j odpowiadających wierszom. Łączymy krawędzią u_i i v_j gdy liczba w polu (i,j) to przynajmniej X. Następnie próbujemy znaleźć w tym nowym grafie C_4, czyli cykl na czterech wierzchołkach. Lub, jeśli ktoś woli, kwadrat.

Mimo przyjemnej grafowej interpretacji, nijak nie zbliżyliśmy się do rozwiązania. Możemy jednak spróbować narysować sobie kilka przykładowych grafów. W szczególności, można spróbować narysować graf, który ma sporo krawędzi, i zastanowić się czy możliwe jest wtedy uniknięcie istnienia kwadratu. Okazuje się, że nie! O ile odpowiednio doprecyzujemy sporo.

Lemat. Każdy graf dwudzielny na wierzchołkach (U,V) i e\geq n+n^{1.5} krawędziach zawiera kopię C_4, gdzie |U|=|V|=n|.

Dowód. Załóżmy sobie, że jest przeciwnie. C_4 składa się z dwóch par krawędzi, które współdzielą jeden koniec, nazwijmy sobie takie pary prawietrójkątami. Bardziej formalnie, prawietrójĸąt to wyróżniony wierzchołek x\in U oraz dwa inne wierzchołki y,z\in V takie, że (x,y) oraz (x,z) są krawędziami. Czyli możemy zauważyc, że mając dwa różne prawietrójkąty z takimi samymi y i z możemy skonstruować C_4. Czyli jeśli nie ma takiego C_4, wszystkich prawietrójkątów może być co najwyżej n \choose 2. Z drugiej strony, ustalając x i wybierając parę jego sąsiadów konstruujemy jeden prawietrójkąt, czyli jeśli stopień x to d_x, wszystkich prawietrójkątów jest dokładnie \sum_{x\in U} {d_x \choose 2}. Mamy więc:

\sum_{x\in U} {d_x \choose 2} \leq {n \choose 2}

lub po drobnym przekształceniu:

\sum_{x\in U} d_x(d_x-1) \leq n(n-1) < n^2

Wiadomo, że \sum_{x\in U} d_x = e, możemy więc spróbować jakoś ograniczyć (z dołu) lewą stronę powyższej nierówności. Okazuje się, że w najgorszym (lub najlepszym, zależy jak patrzeć) przypadku wszystkie d_x są równe, czyli:

n\frac{e}{n}(\frac{e}{n}-1) \leq\sum_{x\in U} d_x(d_x-1) < n^2

czyli tak naprawdę e(e-n) < n^3. Teraz wystarczy tylko rozwiązać nierówność ze względu na e i w nagrodę dostać, że e < \frac{n+\sqrt{n^2+4n^3}}{2} \leq \frac{n+n+2n\sqrt{n}}{2}=n+n^{1.5}.

Jest to dość dobra wiadomość: jeśli nasz graf ma przynajmniej n+n^{1.5} krawędzi, na pewno uda nam się znaleźć C_4. Ale właściwie jak go szukać? Właściwie tak jak wyżej: możemy generować kolejne prawietrójkąty ustalając x i przeglądając pary jego sąsiadów y,z. Gdy tylko zobaczymy jakąś parę y,z po raz drugi, mamy kwadrat. W najgorszym przypadku każdą taką parę zobaczymy dokładnie raz, czyli czas działania całej procedury to tak naprawdę \mathcal{O}(n^2).

To daje nam szybką metodę sprawdzania danego X. Chodzi nam o jego zmaksymalizowanie, czyli wystarczy zastosować wyszukiwanie binarne, by rozwiązać zadanie w czasie \mathcal{O}(n^2\log n). Ale przecież chcieliśmy szybciej?

Wyobraźmy sobie, że mamy listę wszystkich liczb umieszczonych w polach tablicy podanej na wejściu. Posortowaną niemalejąco. Moglibyśmy dodawać odpowiadające im krawędzie jedną po drugiej do aktualnego grafu dwudzielnego i sprawdzać, czy prowadzi to do utworzenia C_4. To sprawdzenie można wykonać bardzo podobnie jak przed chwilą: po prostu przeglądamy wszystkie nowe prawietrójkąty wygenerowane przez kolejną krawędź. Zakładając, że mamy taką posortowaną listę, sumaryczny czas działania to znów \mathcal{O}(n^2), bo każdą parę y,z zobaczymy co najwyżej dwa razy. Problem w tym, że nie mamy takiej posortowanej listy, choć oczywiście możemy ją sobie skonstruować. Problem w tym, że nie umiemy sortować w czasie liniowym.

Na szczęście wcale nie jest to potrzebne. Z udowodnionego wyżej lematu wiemy, że nigdy nie będziemy musieli przetworzyć więcej niż n+n^{1.5} największych liczb. Zamiast sortować wszystkie z nich można by więc wybrać n+n^{1.5} największych, no i posortować tylko te. Jest to o tyle miłe, że wybór k-tego elementu spośród N elementów może być wykonany w czasie \mathcal{O}(N), czyli sumaryczny czas to tylko \mathcal{O}(n^2)+\mathcal{O}((n+n^{1.5})\log n)=\mathcal{O}(n^2). Tak jak obiecałem!

Advertisements

6 myśli nt. „Wartownicy

  1. Lol, magiczne piątki, zabawne :D.
    Swoją drogą, to o ile się nie mylę, to istnieje chyba algorytm w O(n+m) na znajdowanie kwadratu w grafie dwudzielnym, ale on jest jakiś pokręcony, idea podobna do kielichowego, jakieś ściąganie i rozciąganie :P.

  2. Ładnie i mądrze piszesz, ale …
    Piszesz, że pokażesz dla k=3, a pokazujesz dla k=4.
    W innym miejscu piszesz, że czworokąt zbudujesz z C,D i dwóch punktów z A,B,C, a tak naprawdę chodziło chyba o D,E i dwa punkty z A,B,C.

  3. @Wojtek O, ciekawe, a masz może jakiegoś linka lub pamiętasz czyj to jest algorytm?
    @Jakub W tym przypadku chyba lepiej obiecać k=3 i pokazać dla k=4 niż odwrotnie 😛 no ale dzięki za zauważenie.

  4. Tak się zastanawiam (ale niezbyt głęboko bo jeszcze jestem śpiący) czy w obliczu przytoczonych twierdzeń taki naiwny algorytm w którym masz pięc zagnieżdżonych pętli, faktycznie ma złożoność O(n^5) czy też może jednak kończy znacznie wcześniej?
    Przykładowo: powiedzmy, że dwie zewnętrzne pętle ustaliły a=1 i b=2, czyli zupełnie na pałę wybrały dwa punkty. Te dwa punkty wyznaczają prostą która dzieli zbiór wszystkich punktów na dwa zbiory, z których jeden musi być duży. Czy nie jest czasem tak, że w takim dużym zbiorze da się znaleźć zawsze takie trzy punkty, które „pasują” do tamtych dwóch? Innymi słowy: czy nie jest czasem tak, że złożoność to np. O(n^3) ? Pewnie nie, pewnie może być tak, że wszystkie punkty leżą jakby na półokręgu ktory wypina się dupą do tej prostej … anyway, ciekawe czy wśród „naiwnych” algorytmów które przychodzą do głowy komuś kto nie zna tych twierdzeń dałoby się wskazać taki, który „cudem” działa. Np. jeśli algorytm w każdej iteracji losowałby pięć punktów to po jakim czasie trafi?

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s