Název:
Pseudo-triangulace a jejich využití v aplikované výpočetní geometrii
Překlad názvu:
Pseudo-triangulations and their use in applied computational geometry
Autoři:
Trčka, Jan ; Kolcun, Alexej (oponent) ; Kolingerová, Ivana (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2007
Jazyk:
cze
Abstrakt: [cze][eng] V této práci jsou ukázány základní vlastnosti pseudo-triangulace, její užití jako rovinného dělení a implementace algoritmu konstrukce minimální pseudo-triangulace ze vstupní triangulace. Dále je zkoumána možnost využití algoritmu náhodné procházky a navrženy dvě verze algoritmu. Algoritmus procházky je následně použit v inkrementálním algoritmu konstrukce pseudo-triangulace. Všechny nově navržené algoritmy byly ověřeny implementací a experimenty.This thesis shows fundamental properties of pseudo-triangulation, its use as a planar tesselation and implementation of minimal pseudo-triangulation algorithm, which has triangulation as its input. Furthermore, this thesis examines usability of a walking algorithm and two versions of algorithm are proposed. The walking algorithm is also used in an incremental algorithm for a pseudo-triangulation construction. All proposed algorithms have been verified with implementation and experiments.