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

= Písemná =

2.termín (17.1.2020)

Úplně stejný test než (20.1.2016). Upřesnění 4. otázky na Arrangement: Daný arrangement n přímek, napište algoritmus, který vrátí hladinu(level) každé hrany v arrangementu. Hladina je definovaná celkovým počtem přímek „nad“ hranou: kdyby jsme měli vertikální polopřímku začínající na hraně ukazující do z nekonečna, hladina je počet proniknutých přímek. + jaký algoritmus by jste použili jako základ řešení(je to sweep line line segment intersection algorithm, po každém intersection se mění hladina). Cső Emi.

3.termín (28.1.2020)

(zkouška probíhala distančně přes BRUTE, uvádím doslovný přepis otázek)

• [3b] Popište datovou strukturu 1D range tree. Jaké hodnoty jsou v listech a jaké v uzlech a podstromech?
• [4b] Popište Grahamův algoritmus pro konstrukci konvexní obálky množiny bodů. Vysvětlete jeho složitost.
• [3b] Popište typy hran Voronoiova diagramu úseček. U každého typu napište, které časti zadaných úseček je generují.
• [6b] Popište pseudokódem proceduru, která zjistí, které intervaly v intervalovém stromě T protíná zadaný interval (zac kon): QueryInterval(zac, kon, T). Odvoďte časovou složitost dotazu a paměťovou složitost pro uložení intervalového stromu.
• [3b] Napište větu o zóně - co zaručuje při konstrukci arrangementu přímek?
• [6b] Vysvětlete princip datové struktury priority search tree, na jaký typ dotazů se používá a jak se v ní hledá.
• [3b] Vyjmenujte tři vlastnosti duality přímek a bodů a stručně (1-2 větami) je vysvětlete.
• [10b] Napište algoritmus, který pro zadaný odkaz na plošku (face) planárního dělení vypíše všechny plošky, které tvoří souvislý pás po jejím obvodu, tj. všechny plošky, které mají se zadanou ploškou společnou buď obvodovou hranu, nebo společný vrchol. Vícenásobné vypsání jedné plošky nevadí. Planární dělení je uloženo v datové struktuře DCEL.
  • [3b] Nejprve deklarujte datové struktury DCELu potřebné pro běh algoritmu a
  • [5b] poté napište pseudokód algoritmu.
  • [2b] Stanovte časovou a paměťovou asymptotickou složitost navrženého algoritmu.
• [2b] Pro arrangement přímek ve 2D odvoďte maximální počet vrcholů (průsečíků).

= Ústní =

• De Wall triangulace
• Klasifikace data stream model(3 typy)
• Voronoi - smallest width annulus - 3 způsoby konstrukce

25.1.2022

1. Relation between VD and DT.
2. Ham-Sandwich cut, structure, complexity.
3. From given points construct 1D range tree.
4. Trapezoidal Maps. Data Structures. Time and Memory Complexity. [9b]
5. Fortune sweep line algoritmus VD - pojmy beach line, druhy událostí, jak se zpracují tyto události [10b]
6. Memory complexity of line segments in plane.
7. Fractional Cascading - popsat, co setri [3b]
8. Pseudokód algoritmu na horní konvexní obálku přímek.

17.1.2023

1. Ham-sandwich cut
2. VD a DT relace
3. nakreslit 1D range tree
4. Fractional cascading
5. paměťová složitost pro line segment intersection
6. VD furtune sweep line (paměťová složitost, beach line a eventy) [9]
7. Trapezoid map (časová a paměťová složitost, co to je, k čemu to je) [9]
8. Horní envelope přímek alg

24.1.2023

1. Priority search tree (co to je, složitost, k čemu to je)
2. DCEL - definuj, napište alg na nalezení součtu stupňů vrcholů v zadané plošce, jaká bude složitost. (pozor, že se musí projet jak outercomponent, tak i outercomponent)
3. Segment tree - sestav na zadaných úsečkách.
4. Monotónní triangulace: definuj, jak to funguje, složitost.
5. D&C voronoi diagram, složitost „sešití“, jak to spojím.
6. Průsečíky úseček - sweep line - popiš, složitost, jaké máme eventy, mohou nastat najednou?
7. Odvoď maximální počet průsečíků přímek.

Computational geometry: algorithms and applications

Výpisky 2020/21

Soupis algoritmů a složitostí