Drzewa z przypadku

Najwyższy czas na zadanie z geometrii! Nawet miałem upatrzone takie jedno z serii legendarnych, lecz cóż… okazało się zbyt epickie. W zamian proponuję więc dwa problemiki związane z otoczką wypukłą i losowaniem punktów, które być może nie są legendarne, ale chyba można je śmiało nazwać przyjemnymi. Wiem, wiem: geometria? Przyjemne?! Zwariował od tego siedzenia przed monitorem! Ale… sami zobaczycie.

Pierwsze zadanie pochodzi z Uniwersyteckich Zawodów Informatycznych organizowanych (dość regularnie) przez Uniwersytet Jagielloński. Treść jest dość krótka i bezpośrednia: dostajemy n \leq 1000 punktów, każdy z nich ginie z prawdopodobieństwem \frac{1}{2}. Jakie jest oczekiwane pole otoczki wypukłej zbioru punktów, które przeżyły?

Skoro naszym celem jest wyznaczenie oczekiwanego pola wielokąta wypukłego, pewnie warto byłoby zacząć od tego, jak właściwie policzyć pole wielokąta (wypukłego lub nie). Jest na to kilka różnych sposobów, a dokładniej przynajmniej dwa. Obydwa co prawda dość nieprzyjemnie kojarzą się z liczeniem całki, ale nie przejmujmy się tym.

Pierwszy sposób polega na wyobrażeniu sobie, że idziemy po kolejnych krawędziach zgodnie z ruchem wskazówek zegara, i dla każdej z nich dodajemy pole obszaru pod nią (z plusem, jeśli krawędź idzie w prawo, i z minusem, jeśli idzie w lewo), tak jak na lewej części poniższego rysunku. Drugi sposób jest zaś dość zaskakujący. Powiedzmy, że kolejne punkty (zgodnie z ruchem wskazówek zegara) to (x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n), oraz dla uproszczenia notacji zdefiniujmy sobie (x_{n+1},y_{n_1})=(x_1,y_1). Teraz potrzebne nam będzie pojęcie wyznacznika macierzy. Większość z Was pewnie dobrze wie cóż to takiego (unikalna wieloliniowa i antysymetryczna funkcja wierszy, która przyjmuje wartość 1 dla macierzy jednostkowej; chyba?), ale nawet jeśli nie, spokojnie: będziemy operować tylko na macierzach 2 \times 2, dla których \left| \begin{matrix} a & b \\ c & d \end{matrix} \right|=ad-bc. Teraz okazuje się, że pole wielokąta to po prostu:

\displaystyle\frac{1}{2}\sum_{i=1}^{n} \left| \begin{matrix} x_{i+1} & y_{i+1} \\ x_{i} & y_{i} \end{matrix} \right|

Wygląda to odrobinę magicznie, ale wcale takie nie jest. Otóż \left| \begin{matrix} a & b \\ c & d \end{matrix} \right|=ad-bc to nic innego jak dwukrotność pola rozpiętego na wektorach (0,0)\rightarrow (a,b) i (0,0) \rightarrow (c,d). Czyli możemy sobie wyobrazić, że (znów) idziemy po kolejnych krawędziach zgodnie z ruchem wskazówek zegara, no i dla każdej z nich dodajemy pole trójkąta o wierzchołkach w (0,0), (x_i,y_i) i (x_{i+1},y_{i+1}) (z plusem lub z minusem, w zależności od tego, czy wnętrze wielokąta jest na lewo czy na prawo od odcinka (x_i,y_i)\rightarrow (x_{i+1},y_{i+1}). Darujemy sobie formalny dowód tego, że taka procedura da nam prawidłowy wynik, ale tak naprawdę wystarczy popatrzeć chwilę na prawą część poniższego rysunku.

drzewa-pole

No dobra, ale nas interesuje oczekiwane pole. Jest to o tyle kłopotliwe, że przecież kształt otoczki wypukłej istotnie zależy od każdego z punktów. Tutaj przychodzi nam z pomocą powyższy wzór. Otóż wiadomo, że wartość oczekiwana sumy jest sumą wartości oczekiwanych (co proponuję sobie przeliczyć). Niezależnie od tego, które punkty przeżyją, pole otoczki będzie sumą wyrazów postaci \left| \begin{matrix} x_j & y_j \\ x_i & y_i \end{matrix} \right|, gdzie (x_i,y_i) i (x_j,y_j) to jakieś z otrzymanych na wejściu punktów. Można by więc powiedzieć, że nasza szukana wartość jest sumą wszystkich takich wyrażeń, przy czym każde z nich mnożymy przez p_{i,j}, które jest równe 1, gdy punkty (x_i,y_i) i (x_j,y_j) są kolejnymi wierzchołkami na otoczce. No a 0 w przeciwnym wypadku. Teraz zamieniamy wartość oczekiwaną sumy na sumę wartości oczekiwanych, i tak naprawdę dostajemy, że trzeba tylko wyznaczyć wszystkie E[p_{i,j}]!

Lub, przedstawiając kwestię w trochę inny sposób, musimy tylko wyznaczyć dla wszystkich i\neq j szansę na to, że p=(x_i,y_i) i q=(x_j,y_j) są kolejnymi wierzchołkami na otoczce. O wiele łatwiej myśleć o tym, kiedy te dwa punkty NIE są kolejnymi na otoczce. Na pewno tak nie jest, gdy przeżył jakiś inny (x_k,y_k) leżący na odcinku łączącym p i q. Trochę trudniej, ale dalej nietrudno, przekonać się, że jedyny pozostały przypadek to żywy (x_k,y_k), który leży ściśle na lewo od półprostej przechodzącej przez p\rightarrow q, tak jak na poniższej ilustracji.

drzewa-alive

Czyli tak naprawdę umiemy skonstruować zbiór punktów X o następującej własności: p\rightarrow q jest fragmentem otoczki dokładnie wtedy, gdy wszystkie punkty w zbiorze X są martwe (no i gdy p i q takie nie są). Prawdopodobieństwo takiego zbiegu okoliczności to dokładnie \frac{1}{2^{|X|+2}}, więc wystarczy tylko wyznaczyć |X|. Pewnie moglibyśmy w tym celu przejrzeć wszystkie pozostałe punkty, ale.. czy to dobry pomysł?

Może i dobry, ale niezbyt szybki. Procedurę musimy powtórzyć dla wszystkich p i q, czyli otrzymamy sumaryczny czas \mathcal{O}(n^3). Na szczęście można zastosować dość standardową sztuczkę: zamiatanie kątowe (zamiatanie kątów?). Wyobraźmy sobie, że ustalamy punkt p. Dla takiego ustalonego p (dla ułatwienia życia załóżmy sobie, że p=(0,0)) chcemy policzyć |X| odpowiadające wszystkim możliwym wyborom drugiego punktu q. Posortujmy więc wszystkie q względem kąta tworzonego z osią OX i popatrzmy jak różnią się wartości |X| wyznaczane dla kolejnych punktów, dla odmiany w kolejności przeciwnej do ruchu wskazówek zegara. Otóż różnią się, jak widać na poniższej tendencyjnej ilustracji, nieznacznie.

drzewa-angle1

Do poprzedniej wartości należy dodać liczbę punktów w zielonym obszarze, oraz odjąć liczbę w czerwonym. Ilustracja co prawda faktycznie jest nieco tendencyjna, ale nie aż tak bardzo. Skoro punkty rozważamy w kolejności przeciwnej do ruchu wskazówek zegara, czerwony obszar zawsze zawiera tylko jeden punkt (jest to aktualny q). Ten drugi co prawda może zawierać ich dużo więcej, lecz nie jest to problematyczne: żaden punkt nie będzie rozważany dwukrotnie jako zielony. Czyli wystarczy przeglądając kolejne punkty q utrzymywać wskaźnik na pierwszy punkt, który może ewentualnie znaleźć się w zielonym obszarze (lub, mówiąc inaczej, pierwszy, który znajduje się ściśle na prawo od odcinka p \rightarrow q. Po przejściu do kolejnego q przesuwamy wskaźnik tak długo jak jest to potrzebne, no i uaktualniamy |X|. Zakładając, że mamy już posortowane punkty, cały proces zajmie nam tylko czas \mathcal{O}(n). No a sortowanie… wiadomo ile zajmie.

Całą sztuczkę musimy powtórzyć dla wszystkich możliwych p, czyli dostajemy sumaryczną złożoność \mathcal{O}(n^2\log n). Niby fajnie. Implementacja nie jest może bardzo przyjemna (trzeba trochę uważać przy sortowaniu punktów, które są współliniowe, nie jest to jednak bardzo ciekawe i darujemy sobie bardziej szczegółowe rozważania), ale nie jest też dramatycznie skomplikowana. Ale… czy da się szybciej?

Da się! Korzystając z pewnej dość standardowej (dla geometrów, zwłaszcza tych obliczeniowych) sztuczki można zmniejszyć czas działania do \mathcal{O}(n^2). Jednak my spojrzymy na problem zupełnie inaczej.

Otóż autor (lub może autorzy, ciężko poznać) zadania oczekują od nas podania odpowiedzi z dokładności do 0.001. Nie zdradzają niestety, czy chodzi tutaj o dokładność względną czy bezwzględna, no ale załóżmy, że o tę drugą. W dodatku obiecują, że |x_i|,|y_i| \leq M=1000.

Wróćmy do naszego rozwiązania. Sumaryczny wynik to nic innego jak suma wyrazów postaci \left| \begin{matrix} x_j & y_j \\ x_i & y_i \end{matrix} \right| \frac{1}{2^{|X|+2}}. Skoro interesuje nas podanie wartości tej sumy z dokładnością do \epsilon, tak naprawdę możemy z czystym sumieniem zignorować wyrazy, które są bardzo małe! Jak małe? Pewnie mniejsze niż \frac{\epsilon}{n^2}. Jest to bardzo dobra wiadomość, bo przecież \frac{1}{2^{|X|+2}} to bardzo mała liczba. No, o ile tylko |X| jest rzędu, powiedzmy, 100.

Po chwili prostych rachunków otrzymujemy, że interesują nas tylko pary i,j, dla których |X| < \log \frac{n^2M^2}{\epsilon}, czyli dla limitów z treści zadania |X|<50. Czy może się zdarzyć tak, że takich par będzie dużo? A nawet jeśli nie, to czy umielibyśmy sprawnie "wyłuskać" te, które są dla nas interesujące?

Ustalmy sobie jakiś punkt p=(x_i,y_i) i popatrzmy na wszystkie możliwe q=(x_j,y_j), które leżą na prawo i na lewo. Jeśli posortujemy je kątowo, widać, że interesuje nas tylko ostatnich 50, tak jak na poniższym rysunku.

drzewa-last

No dobra, ale jak dobrać się do tych ostatnich 50 punktów unikając sortowania wszystkich?

W tym miejscu warto pomyśleć o cebuli. Naprawdę. A dokładniej o jej obieraniu. Powiedzmy, że znajdziemy i usuniemy otoczkę naszego zbioru punktów. Następnie znajdziemy i usuniemy otoczkę jego pozostałej części. I tak dalej. Uzyskamy w ten sposób partycję całego zbioru na pewną liczbę wielokątów wypukłych. Teraz jeśli nasz punkt p należy do k-tego z nich, licząc od zewnątrz, niezależnie od wyboru q na pewno będziemy mieli k\ leq |X|. Odrobinę uogólniając to rozumowanie (co pewnie wymaga chwili zastanowienia) dostajemy, że tak naprawdę można pozbyć się wszystkich punktów, które nie należą do jednej z 50 zewnętrznych otoczek.

drzewa-cebula

Jest o tyle wesołe, że wyznaczenie podziału na otoczki nie jest wcale takie proste. Każdą z nich można znaleźć w czasie liniowym, ale w najgorszym przypadku nasz podział może mieć nawet \frac{n}{4} elementów. No ale, skoro interesuje nas tylko 50 zewnętrznych, wystarczy powtórzyć obieranie 50 razy. Co dalej?

Dalej jest już prosto, przynajmniej w teorii. Wróćmy do ustalonego p i tych q, które są na prawo i na lewo. Skoro podzieliliśmy wszystkie punkty na 50 otoczek, w szczególności każdy możliwy punkt q należy do jednej z nich. Co więcej, punkty q leżace na jednej otoczce można bardzo łatwo posortować kątowo: tak naprawdę są one już posortowane! Czyli tak naprawdę możemy myśleć, że mamy 50 posortowanych ciągów, no i chcemy wybrać z nich 50 największych elementów, co można dość łatwo wykonać używając dowolnej kolejki priorytetowej.

Jaki z tego wniosek? Przy odrobinie staranności możemy uzyskać złożoność \mathcal{O}(n\log \frac{n^2M^2}{\epsilon} \log\log\frac{n^2M^2}{\epsilon}). Pewnie niepraktyczne, ale.. fajne, nie?

To było jedno z obiecanych dwóch zadań. Drugie jest dość świeże: jest to zadanie D z CROC round 2 przeprowadzonej na Codeforces. Dostajemy w nim wielokąt wypukły, a w zamian powinniśmy wypisać oczekiwane pole kwadratu, którego przekątna łączy dwa z losowo wybranych punktów o współrzędnych całkowitych, które należą do środka lub obwodu rzeczonego wielokąta.

Sparsowanie powyższego zdania pewnie wymaga pewnej ostrożności, ale mam nadzieję, że wszystkim się udało. Jeśli dwa losowo wybrane punkty to (x,y) i (x',y'), łączący je odcinek ma długość \sqrt{(x-x')^2+(y-y')^2}, czyli skonstruowany kwadrat ma pole \frac{(x-x')^2+(y-y')^2}{2}. Skoro interesuje nas wartość oczekiwana, znów możemy skorzystać z jego liniowości! Czyli tak naprawdę interesuje nas wyznaczenie oczekiwana wartość (x-x')^2 oraz (y-y')^2. Sytuacja wydaje się być całkowicie symetryczna, więc skupmy się na pierwszej z nich.

(x-x')^2=x^2-2xx'+x'^2. Ufff. No to możemy sobie jeszcze raz skorzystać z liniowości wartości oczekiwanej! I otrzymać, że musimy wyznaczyć trzy wartości:

  1. liczbę punktów o współrzędnych całkowitych, które należą do środka lub odwodu naszego wielokąta,
  2. oczekiwaną wartość x^2 po wszystkich takich punktach,
  3. oczekiwaną wartość 2xx' po wszystkich parach takich punktów (no, tak naprawdę po parach różnych punktów, lecz uważny Czytelnik na pewno zauważy, że to tylko taka, hm, nieistotna kłoda pod nogi).

W tym momencie musimy trochę bliżej przyjrzeć się limitom na rozmiar wejście. Nasz wielokąt ma nie więcej niż 10^5 wierzchołków, ponadto współrzędne jego wierzchołków są z zakresu [-10^6,10^6]. Ta pierwsza wiadomość nie jest szczególnie ciekawa, za to ta druga… hm.

Od razu widzimy, że liczba interesujących nas punktów może być nawet rzędu 10^{12}. Jest to, jak by nie patrzeć, całkiem spory rząd. Jednak ponieważ wielokąt jest wypukły, wszystkie interesujące nas punkty z ustaloną współrzędną x tworzą spójny przedział [y_1,y_2]! Co więcej, ten przedział można dość łatwo wyznaczyć wystarczy tylko chytrze wyszukać ten odcinek otoczki, który jest „nad”, oraz ten, który jest „pod”. Mając [y_1,y_2], możemy uaktualnić c i oczekiwaną wartość x^2. Trochę gorzej wygląda kwestia uaktualnienia oczekiwanej wartości 2xx'. Jeśli jednak wyobrazimy sobie, że rozważamy kolejne wartości x idąc od lewej do prawej, możemy utrzymywać sumę wszystkich x' na lewo. To tak naprawdę pozwoli nam na uaktualnienie oczekiwanej wartości 2xx' uwzględniając wszystkie punkty z aktualną wartością x i x'\leq x. Te wszystkie operacje można wykonać w czasie stałym za pomocą kilku operacji arytmetycznych.

Pozostaje tylko chytrze wyszukać odpowiednie odcinki otoczki. Jest tutaj kilka możliwości. Można skorzystać z wyszukiwania binarnego, co pewnie nie jest bardzo fajnie: dorzuca nam dodatkowy czynnik logarytmiczny. Można też popatrzeć na pytanie od tak zwanej.. drugiej strony, i dla ustalonego odcinka przejrzeć wszystkie x, dla których ten odcinek jest „nad”. W ten sposób można uzyskać rozwiązanie, które działa w czasie \mathcal{O}(n+M), gdzie M jest zakresem współrzędnych. No i pięknie. Wydaje mi się, że można trochę lepiej, ale zostawimy sobie tę przyjemność na inną okazję.

Nie będę się upierał, że techniczne szczegóły obydwu rozwiązań są szczególnie podniecające, jednak warto zapamiętać trik z liniowością wartości oczekiwanej. Jest równie prosty co przydatny!

Na koniec proponuję jeszcze żart-zagadkę (no dobra, element żartu jest raczej minimalny). Powiedzmy, że losujemy (niezależnie i jednostajnie) n punktów w kwadracie [0,1] \times [0,1]. Jaka jest oczekiwana liczba punktów, które nie są w środku otoczki wypukłej? A co jeśli punkty losujemy (znów, niezależnie i jednostajnie) z koła o środku w (0,0) i promieniu 1? I… dlaczego?

Advertisements

Jedna myśl nt. „Drzewa z przypadku

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