Zagadnienia

1. Wypukła otoczka w R^2 - algorytm Chana. //Mount
2. Dolne oszacowanie dla problemu wypukłej otoczki, problem CHSV (Convex Hull Size Verification). //Mount
3. Przecinanie się odcinków na płaszczyźnie. //deBerg 2.1
4. Reprezentacja podziału płaszczyzny - podwójnie wiązana lista krawędzi (DCEL) //deBerg 2.2
5. Nakładanie podziałów płaszczyzny. //deBerg 2.3
6. Diagramy Voronoi: własności, algorytm zamiatania (Fortune) //deBerg 7.1, 7.2
7. Problem galerii i triangulacja wielokąta, podział wielokąta na fragmenty monotoniczne. //deBerg 3.1, 3.2
8. Lokalizacja punktu: mapy trapezowe, algorytm przyrostowy. //deBerg 6.1, 6.2
9. Otoczka wypukła w R^3. //deBerg 11.1, 11.2
10. Dualność, układy prostych na płaszczyźnie. //deBerg 8.2, 8.3
11. Przeszukiwanie obszarów ortogonalnych, kd-drzewa. //Mount
12. Wielowymiarowe drzewa obszarów, kaskadowanie cząstkowe. //Mount
13. Drzewa BSP, konstrukcja, algorytm malarza. //deBerg 12.1, 12.2, 12.3

Przykładowe pytania egzaminacyjne

Podaj zwięzłą odpowiedź:

Algorytm Chana (znajdowanie wypukłej otoczki w R^2):
- jaka wielkość zmieniana jest (iterowana) w zewnętrznej pętli algorytmu (czyli w głównej iteracji)?
- jakie przyjmuje kolejne wartości?
- jak przekłada się to na złożoność?

Znajdowanie przecięć odcinków na płaszczyźnie:
- w jaki sposób osiągamy to, że wielkość wyniku nie ma wpływu na asymptotyczny koszt pamięciowy?

Algorytm znajdowania wypukłej otoczki w R^3:
- zdefiniuj graf konfliktów G
- jak wygląda dodawanie nowych krawędzi do G i skąd wynika poprawność tego fragmentu algorytmu?

Przeszukiwanie obszarów ortogonalnych:
- napisz równanie rekurencyjne opisujące czas wyszukiwania w kd-drzewie i uzasadnij jego poprawność

Zaznacz poprawne:

W dowodzie dolnego oszacowania na złożoność algorytmów znajdowania wypukłej otoczki wykorzystuje się (niekoniecznie bezpośrednio)
- twierdzenie ograniczające od dołu wysokość decyzyjnego drzewa algebraicznego
- redukcję problemu wypukłej otoczki do problemu weryfikacji rozmiaru multizbioru
- własności drzew decyzyjnych z wyłącznie liniowymi funkcjami testu.

W algorytmie obliczania diagramu Voronoi (Fortune)
- w danym położeniu prostej zamiatającej, przecięcie diagramu z półpłaszczyzną powyżej prostej jest reprezentowane w aktualnej strukturze DCEL
- obsługa pojedynczego zdarzenia typu okrąg może trwać czas proporcjonalny do lg^2n
- (w ogólnym położeniu) zdarzenie punktowe może wygenerować wierzchołek diagramu

W lokalizacji punktu metodą trapezów, struktura mapy trapezowej T(S) i struktura przeszukiwania D mają następujące własności:
- kolejność wstawiania odcinków ma wpływ na postać obu struktur
- pesymistycznie, rozmiary obu struktur są takie same
- w średnim przypadku, rozmiary obu struktur są takie same
- oczekiwany czas konstrukcji struktury D jest większy niż jej oczekiwany rozmiar