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

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

Computational geometry: algorithms and applications