Obserwator

Tym razem znów krótko, ale za to w trzech wymiarach! (Tak naprawdę w dwóch i pół, więc nie musicie szukać okularów.) Celem będzie podzielenie danego zbioru punktów na dwa mniejsze tak, aby średnica każdego z utworzonych zbiorów była mniejsza niż średnica tego oryginalnego.

Zadanie pojawiło się dawno temu na Uniwersyteckich Zawodach Informatycznych organizowanych przez Uniwersytet Jagielloński (treść możecie zobaczyć tutaj, choć chyba trzeba się wcześniej zarejestrować), ale zostało niedawno „odgrzane” w związku z obozem w Petrozavodsku. I słusznie, bo jest całkiem fajne! Wracając do treści, ważne jest to, że liczba punktów w zbiorze nie przekracza 10^5 (co pewnie nie jest bardzo ciekawe), średnica zbioru to największa z odległości między dwoma jego elementami (co na pewno nie jest ciekawe) oraz każdy z podanych punktów ma trzy współrzędne. To ostatnie jest wręcz intrygujące, jednak nie warto się za bardzo ekscytować: już w kolejnym zdaniu autor obiecuje, że każdy z podanych punktów leży na płaszczyźnie x+y+z=0. Po chwili refleksji może się to wydać dość dziwaczne. Skoro wszystkie punkty leżą na jednej płaszczyźnie, równie dobrze można by tę płaszczyznę obrócić tak, aby zawsze z=0. Trochę tak, a trochę nie: wrócimy do tej kwestii już za chwilę, na razie załóżmy jednak, że punkty mają podane tylko dwie współrzędne, czyli myślimy o przypadku 2D.

Skoro interesuje nas średnica zbioru punktów, to pewnie fajnie byłoby umieć ją szybko wyznaczyć. Jak pewnie wiecie, średnicę zbioru n punktów można wyznaczyć w czasie \mathcal{O}(n\log n). Pierwszym krokiem jest zauważenie, że punkty, które maksymalizują odległość, leżą na otoczce wypukłej całego zbioru. Możemy więc wyznaczyć otoczkę i wywalić wszystkie punkty, które nie są jej wierzchołkami. Dalej jest troszkę trudniej. Kuszące wydaje się powiedzenie, że dla każdego z wierzchołków otoczki wyznaczamy drugi wierzchołek, który jest jak najdalej. Nie jest to jednak takie proste, gdyż wcale nie jest tak, że taki drugi wierzchołek jest jeden: wystarczy wyobrazić sobie elipsę.

No dobrze, czyli wyznaczanie najlepszego „partnera” dla każdego wierzchołka otoczki z osobna nie jest najlepszym pomysłem. Pomocny okazuje się tutaj eksperyment (myślowy; przecież nie będziemy odchodzić od monitora). Uwierzmy bowiem, że wystrugaliśmy z drewna (być może trochę koślawe) koło w kształcie naszej otoczki wypukłej. Następnie przetaczamy je po prostej tak jak na poniższej ilustracji.

obserwator1

Podczas całej operacji zwracamy uwagę na to, który z wierzchołków jest najwyżej nad poziomem „gruntu”. Utrzymywanie tej informacji jest dość proste, bowiem na samym początku możemy wyznaczyć ją naiwnie, a następnie zauważyć, że po lekkim obróceniu wielokąta być może należy przejść do wierzchołka, który jest poprzednikiem aktualnego. Równie proste jest przekonanie się o tym, że ta informacja tak naprawdę daje nam odpowiedź na pytanie, jakie są dwa najbardziej odległe punkty na otoczce. Jest bowiem tak, że wysokość dowolnego wierzchołka na otoczce nie może być większa niż jego odległość od wierzchołka, na którym opiera się w danym momencie cały wielokąt. Jest również tak, że jeżeli popatrzymy się na dwa wierzchołki otoczki, które są w odległości d, ustawienie wielokąta tak, aby łączący je odcinek był pionowy spowoduje, że wysokość najwyższego wierzchołka na otoczce będzie równa przynajmniej d.

Opisany wyżej proces śledzenia najwyższego wierzchołka można zasymulować w czasie liniowym od rozmiaru otoczki. Wystarczy zauważyć, że istotne są dla nas tylko te momenty, w których zmienia się wierzchołek, który jest aktualnym punktem podparcia, lub wierzchołek, który maksymalizuje wysokość. Dla każdej takiej sytuacji dostajemy parę punktów, która jest kandydatem na średnicę.

Wrócmy do zadania. Znając średnicę podanego zbioru (oznaczmy ją sobie jako D), chcemy podzielić go na dwie części tak, ab średnica każdej z nich była mniejsza niż D. Istotne jest tutaj to, że nie przejmujemy się za bardzo tym, jak bardzo mniejsze będą te nowe średnice. Wystarczy, że zjedziemy chociaż o epsilon poniżej D.

Zacznijmy od prostej obserwacji: bez straty ogólności można przejmować się tylko wierzchołkami otoczki. Jest tak dlatego, że odległość między dwoma punktami, z których choć jeden nie jest wierzchołkiem otoczki, jest na pewno ściśle mniejsza niż D. (Być może warto to sobie udowodnić.) Czyli zostajemy z następującym problemem: chcemy pomalować wierzchołki otoczki na dwa kolory tak, aby żadne dwa wierzchołki tego samego koloru nie były w odległości dokładnie D. Brzmi znajomo?

Pewnie tak. Tak naprawdę chcemy sprawdzić, czy jakiś graf jest dwudzielny. Co trudne raczej nie jest… o ile graf jest podany w jakiś rozsądny sposób. Nasza sytuacja jest niestety nieco inna: graf jest podany dość niejawnie. Nie jest to jednak wielki problem, gdyż dość łatwo możemy wypisać wszystkie pary wierzchołków otoczki, które są w odległości dokładnie D. Wystarczy tylko przypomnieć sobie całą sztuczkę z przetaczaniem wielokąta. Jeśli dana para wierzchołków jest w odległości dokładnie D, to prędzej lub później jeden z nich będzie punktem podparcia, a drugi tym, który maksymalizuje wysokość. Symulacja całego procesu pozwala nam więc na wygenerowanie wszystkich takich par, i co nawet lepsze pokazuje, że jest ich niewiele, bo nie więcej niż liniowo od rozmiaru otoczki.

Zredukowaliśmy więc całe zadanie do sprawdzania, czy skonstruowany graf jest dwudzielny. Ponieważ zarówno liczba wierzchołków jak i krawędzi tego grafu jest liniowa od rozmiaru otoczki, złożoność całego rozwiązania jest liniowa, plus czas potrzebny na wyznaczenie otoczki.

No dobrze, ale przecież w oryginalnej treści punktu co prawda leżą w jednej płaszczyźnie, ale mają podane trzy współrzędne. Czy przypadkiem nie utrudni nam to implementacji? Okazuje się, że nawet nie tak bardzo. W całym rozwiązaniu w zasadzie możemy bowiem operować na rzutach punktów na płaszczyznę z=0 (prawie; odległość między parą punktów lepiej liczyć w 3D). Więc właściwie dlaczego autor zdecydował się na to wydawałoby się sztuczne utrudnienie? Wbrew pozorom ma to sens, co pozostawiam jako zagadkę dla Czytelnika.

Advertisements

3 myśli nt. „Obserwator

  1. To x+y+z=0 jest po to, aby istniały nieparzyste cykle – na płaszczyźnie z=0 się nie znajdzie nieparzystokąta o bokach równej długości w wierzchołkach w pktach kratowych :).
    A na x+y+z = 0 już istnieje np. (1, -1, 0) cyklicznie obrócone. Nasuwa się jednak pytanie – czy istnieją nieparzyste cykle różne od trójkątów?

  2. No to pytanie jest… intrygujące. Mi się wydaje, że nie istnieją, ale nie mam dowodu 🙂 Wydaje mi się, że wystarczy pokazać, że nie da się „upchnąć” regularnego k-kąta w wymiernych punktach w 3D, gdzie k>3 i k jest nieparzyste. Dla k=5 jest chyba łatwo, no bo jeśli wierzchołki są wymierne, to wymierne są też przecięcia przekątnych. Ale każda przekątna jest dzielona przez inne w stosunku 1 : \phi, czyli niewymiernym… co chyba prowadzi do sprzeczności. Dla wyższych k może i jest podobnie, ale nie bardzo wiem jak to przeliczyć.

  3. Ja właśnie chyba bym tak nie szarżował ze stwierdzeniem, że one muszą być foremne. Wiele nieforemnych wypukłych 5kątów ma wszystkie przekątne równej długości.

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