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. 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

Computational geometry: algorithms and applications