Výpočetní geometrie

• Stránky předmětu: https://cw.felk.cvut.cz/wiki/misc/projects/oppa_oi_english/courses/ae4m39vg/start
• Přednášející: Petr Felkel
• Cvičící: Petr Felkel

• 1. úloha
• 3. úloha

Na zkoušce se prověřují teoretické znalosti v plném rozsahu odpřednášené a odcvičené látky.

V otázkách nebylo nic z odcvičené látky. Jen z přednášek = Písemná =

1.termín

1. Vysvětlit rozdíl mezi složitostí algoritmu a složitostí problému, který z nich může být větší, od obou příklad
2. Popsat DCEL strukturu(detailně)
3. Popsat vysledek counting query a report query, který z nich lze implementovat rychleji(více efektivněji)+příklad od každého
4. Popsat metodu slabs k hledání úseček v rovině, popsat operační a paměťovou složitost. Porovnat s metodou „trapezoid subdivison“
5. Popsat princip 2D range tree(co je v listech a vnitrnich uzlech, co je v kanonických množinách v druhém stromě), nakreslete příklad 2D range tree s pár elementy
6. Popsat Grahamův algoritmus pro konstrukci konvexní obálky, jaká je operační složitost předprocesní fáze a jaká samotné konstrukce?
7. Popsat pár slovy princip inkrementální konstrukce straight line
8. Vysvětlit princip konstrukce Voronoi diagramu pomocí rozděl a panuj
9. Vysvětlit algoritmus inkrementálního Delaunay triangulace a vysvětlete operace flip edge a legalize edge

2.termín

1. Vytvořit nad danými čísly 1D range tree a přiřadit kanonické množiny uzlům
2. Jak se spočítá orientovaná plocha trojúhelníku, jak se využije k určení leftturn
3. Jaká je souvislost VD a DT?
4. Jaká je struktura u lichoběžníkových map pro vyhledávání, jakou má složitost
5. Fortune sweep line algoritmus - pojmy beach line, druhy událostí, jak se zpracují tyto události
6. Z jakých objektů se skládá Voronoi diagram úseček
7. Pseudoalgoritmus na dolní konvexní obálku přímek

= Ústní =

1. Kde se objevuje pojem Zona?
2. Vysvětlit kanonické množiny
3. Popsat DCEL

Letos byly dva termíny, další se nevypsal, pokud vim. Nakonec to dal skoro všem, i když písemná tomu vůbec nenapovídala: strana 1, strana 2

= Písemná =

2.termín

• Napište algoritmus pro výpis koncových bodů hran v DCEL, které mají společný bod (složitosti napsat).
• Fortune sweep line algoritmus - pojmy beach line, druhy událostí, jak se zpracují tyto události.
• Popsat triangulaci monotoního polygonu.
• Vytvořit Voronoi diagram pro 5 úseček, jaké geometrické útvary využíváme.
• Popište metodu legalizace hrany.
• Vytvořte segment tree pro zadané intervaly.
• Pseudoalgoritmus na dolní konvexní obálku přímek.
• Něco ohledně sweep line v Arrangements of lines (paměťové složitosti). * Nečíslovaný seznam

3.termín

1. Vyčíslit kolik vznikne maximálně hran při uspořádání úseček.
2. Napsat algoritmus který převede nemonotoní polygon na monotoní.
3. Vytvořit segmentový strom zadaných úseček.
4. Vymyslet algoritmus, který spočítá délku všech hran zadané plochy, s využitím DCELu.
5. Algoritmus De Wall, k čemu slouží, jak vytvoří první trojúhelník.
6. Popsat sweep line algoritmus pro detekci průsečíků úseček, události složitost atd..
7. Popsat D&C algoritmus pro vytvoření konvexní obálky, složitosti jak se hledají tangenty.
8. Princip priority search tree, k čemu slouží, jak se v něm hledá.

= Písemná =

2.termín (8.1.2015), evidentně stejné jako 2.termín 2014!

1. Paměťová složitost arrangementu přímek. Odpověď rozdělit na pam. slož. pro frontu událostí, stav podél sweep line. Výsledek vysvětlit. (3b)
2. Navrhnout algoritmus: Pro DCEL a půlhranu vypíše koncové body všech půlhran, které vychází ze stejného počátečního vrcholu. Deklarujte datové struktury pro DCEL, dat. struk. pro běh algoritmu. Napsat pseudokód, napsat jeho složitost. (7b)
3. Triangulace monotoního polygonu. (3b)
4. Co je to legalizace hrany u Delaunay triangulace. (3b)
5. Udělat segmentový strom (bylo tam 6 segmentů, tři v jedné úrovni nahoře, tři v druhé úrovni dole) (5b)
6. Vysvělete Fortune Sweep Line algoritmus. Beach line, typy událostí, postup jejich zpracování. (10b)
7. Z jakých geometrických útvarů se skládá Voronoi diagram izolovaných úseček? Nakreslit příklad Voronoi diagramu pro 5 úseček. (5b)
8. Pseudokód algoritmu konstrukce dolní obálky množiny přímek (3b)

3.termín (14.1.2015), ústní cca za 3h od skončení písemné

1. DCEL: máme zadanou stěnu, napsat algoritmus který vypíše všechny hrany, které incidují z vrcholů této stěny. Datové struktury DCEL, složitost algoritmu. (10b)
   • POZOR, algoritmus který obejde stěnu a vypíše hrany které jí tvoří nestačí - to bylo hodnoceno 5b.
2. Datová struktura u Overmars algoritmu - popsat (4b)
3. 3 případy které můžou nastat při vkládání do Trapezoidal Map. Nakreslit, popsat jak se změní point location struktura. (6b)
4. Navrhnout algoritmus, který v arrangementu každé úsečce přiřadí číslo od 0 do n-1, které vyjadřuje, kolik přímek je nad ní. Vyjdetě z (nějakého podobného) existujícího algoritmu. (9b)
5. Interval tree pro 6 segmentů (3b)
6. Definice D-simplexu (1b)
7. Co je to graf konfliktů, co je v něm na začátku, co je v něm na konci, co umožňuje (4b)
8. Vzorec pro maximální počet oblouků u Fortune Sweep Algoritmu a nakreslit takový případ (3b)

= Ústní =

1. Range search, na co se používá, nakreslit range tree, co jsou kanonické množiny
2. Kd stromy
3. Order-k Voronoi Diagram, Farthest-point
4. Dual graf pro Voronoi diagram, Delaunay graf, legalizace hrany

= Písemná =

1.termín (20.1.2016)

• Fractional Cascading - popsat, co setri (3 b.)
• Quick Hull - popsat, slozitosti a pripady, kdy k nim dochazi (4 b.)
• Sweep Line algoritmus pro ziskani pruseciku usecek - nakreslit pripad, kdy v jednom bode nekolik usecek konci, zacina a bodem prochazi, jak se tento pripad osetri (6 b.)
• Arrangement - oznacit hrany cislem, ktere znamena pocet primek nad hranou (neco s hladinou - level, doplnte, tohle jsem netusil) (9 b.)
• Interval Tree - dany nakreslene intervaly, udelat k nim interval tree (jako obr. 10.3, str. 223 v de Bergovi 3rd ed.) (3 b.)
• Definice planarniho deleni (2 b.)
• Test pruniku intervalu - dany dva intervaly (x1, y1), (x2, y2), napsat kod podminky, ktera zjisti, zda se protinaji (2 b.)
• Konstrukce Trapezoidove mapy, cim je zajisteno, aby pruchod byl O(log n) (2 b.)
• DCEL - nadefinovat struktury a pak napsat kod, ktery pro danou plosku vypise vsechny plosky, ktere s ni sousedi (pres hranu nebo bod vstupni plosky), nevadi, pokud se nejaka ploska vypise vickrat (9 b.)

2.termín (27.1.2016)

• Maximální počet hran v arrangementu přímek - odvodit složitost. (2b)
• Monotenizace polygonu - popsat algoritmus. (4b)
• Vytvořit segment tree pro 6 úseček. (5b)
• DCEL - vypsat součet délek hran které incidují se stěnou. (7b)
• Algoritmus DeWall - k čemu slouží, jak nalezne první trojúhelník. (3b)
• Popsat algoritmus sweep line úseček. (8b)
• Vysvětlit princip Priority Search Tree a jak se v něm hledá. (6b)
• Metoda rozděl a panuj - vysvětlit, odůvodnit složitosti, včetně složitosti hledání sešívacích čar. (5b)

= Ústní =

• Konvexni obalky - jake znam algoritmy, jejich slozitosti, pouzitelnost ve 3D, paralelizovatelnost
• Dualita - v cem spociva, jak se da vyuzit; mluvil jsem o vypoctu kolinearity bodu, ze jde vypocist prevedenim do dualniho prostoru a vypoctem pruseciku, kdyz se to pocita normalne, tak je to O(n^3), takhle O(n^2)
• Duální struktura k Voronoi Diagramu - co to je apod., nakreslit příklad, legalizace hrany, …
• Trapezoid maps - co to je, porovnat s metodou pásů - chtěl hlavně kombinatorickou složitost porovnat, PŘESNĚ zdůvodnit paměťové nároky

Computational geometry: algorithms and applications