====== 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í: [[http://dcgi.felk.cvut.cz/en/members/felkepet|Petr Felkel]] * Cvičící: Petr Felkel ===== Cvičení ===== * [[courses/a4m39vge/uloha1|1. úloha]] * [[courses/a4m39vge/uloha3|3. úloha]] ===== Zkouška ===== Na zkoušce se prověřují teoretické znalosti v plném rozsahu odpřednášené a odcvičené látky. == 2013 == V otázkách nebylo nic z odcvičené látky. Jen z přednášek = Písemná = **1.termín** - 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 - Popsat DCEL strukturu(detailně) - Popsat vysledek counting query a report query, který z nich lze implementovat rychleji(více efektivněji)+příklad od každého - Popsat metodu slabs k hledání úseček v rovině, popsat operační a paměťovou složitost. Porovnat s metodou "trapezoid subdivison" - 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 - Popsat Grahamův algoritmus pro konstrukci konvexní obálky, jaká je operační složitost předprocesní fáze a jaká samotné konstrukce? - Popsat pár slovy princip inkrementální konstrukce straight line - Vysvětlit princip konstrukce Voronoi diagramu pomocí rozděl a panuj - Vysvětlit algoritmus inkrementálního Delaunay triangulace a vysvětlete operace flip edge a legalize edge **2.termín** - Vytvořit nad danými čísly 1D range tree a přiřadit kanonické množiny uzlům - Jak se spočítá orientovaná plocha trojúhelníku, jak se využije k určení leftturn - Jaká je souvislost VD a DT? - Jaká je struktura u lichoběžníkových map pro vyhledávání, jakou má složitost - Fortune sweep line algoritmus - pojmy beach line, druhy událostí, jak se zpracují tyto události - Z jakých objektů se skládá Voronoi diagram úseček - Pseudoalgoritmus na dolní konvexní obálku přímek = Ústní = - Kde se objevuje pojem Zona? - Vysvětlit kanonické množiny - 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: [[courses/a4m39vge/strana 1]], [[courses/a4m39vge/strana 2]] == 2014 == = 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** - Vyčíslit kolik vznikne maximálně hran při uspořádání úseček. - Napsat algoritmus který převede nemonotoní polygon na monotoní. - Vytvořit segmentový strom zadaných úseček. - Vymyslet algoritmus, který spočítá délku všech hran zadané plochy, s využitím DCELu. - Algoritmus De Wall, k čemu slouží, jak vytvoří první trojúhelník. - Popsat sweep line algoritmus pro detekci průsečíků úseček, události složitost atd.. - Popsat D&C algoritmus pro vytvoření konvexní obálky, složitosti jak se hledají tangenty. - Princip priority search tree, k čemu slouží, jak se v něm hledá. == 2015 == = Písemná = ** 2.termín (8.1.2015), evidentně stejné jako 2.termín 2014! ** - 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) - 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) - Triangulace monotoního polygonu. (3b) - Co je to legalizace hrany u Delaunay triangulace. (3b) - Udělat segmentový strom (bylo tam 6 segmentů, tři v jedné úrovni nahoře, tři v druhé úrovni dole) (5b) - Vysvělete Fortune Sweep Line algoritmus. Beach line, typy událostí, postup jejich zpracování. (10b) - 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) - 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é ** - 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. - Datová struktura u Overmars algoritmu - popsat (4b) - 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) - 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) - Interval tree pro 6 segmentů (3b) - Definice D-simplexu (1b) - Co je to graf konfliktů, co je v něm na začátku, co je v něm na konci, co umožňuje (4b) - Vzorec pro maximální počet oblouků u Fortune Sweep Algoritmu a nakreslit takový případ (3b) = Ústní = - Range search, na co se používá, nakreslit range tree, co jsou kanonické množiny - Kd stromy - Order-k Voronoi Diagram, Farthest-point - Dual graf pro Voronoi diagram, Delaunay graf, legalizace hrany == 2015 == = 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 ===== Literatura ===== [[http://www.scribd.com/doc/7619913/Computational-Geometry-Algorithms-and-Applications-2d-Ed-De-Berg|Computational geometry: algorithms and applications ]] ~~DISCUSSION~~