navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m39vge [2016/01/20 20:29] papouada [Zkouška] |
courses:a4m39vge [2025/01/03 18:23] (aktuální) |
||
|---|---|---|---|
| Řádek 95: | Řádek 95: | ||
| - Order-k Voronoi Diagram, Farthest-point | - Order-k Voronoi Diagram, Farthest-point | ||
| - Dual graf pro Voronoi diagram, Delaunay graf, legalizace hrany | - Dual graf pro Voronoi diagram, Delaunay graf, legalizace hrany | ||
| + | |||
| + | == 2015 == | ||
| + | = Písemná = | ||
| ** 1.termín (20.1.2016) ** | ** 1.termín (20.1.2016) ** | ||
| Řádek 106: | Řádek 109: | ||
| * Konstrukce Trapezoidove mapy, cim je zajisteno, aby pruchod byl O(log n) (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.) | * 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í = | = Ústní = | ||
| * Konvexni obalky - jake znam algoritmy, jejich slozitosti, pouzitelnost ve 3D, paralelizovatelnost | * 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) | * 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 ===== | ===== Literatura ===== | ||
| [[http://www.scribd.com/doc/7619913/Computational-Geometry-Algorithms-and-Applications-2d-Ed-De-Berg|Computational geometry: algorithms and applications ]] | [[http://www.scribd.com/doc/7619913/Computational-Geometry-Algorithms-and-Applications-2d-Ed-De-Berg|Computational geometry: algorithms and applications ]] | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
