Original title:
Pseudo-triangulace a jejich využití v aplikované výpočetní geometrii
Translated title:
Pseudo-triangulations and their use in applied computational geometry
Authors:
Trčka, Jan ; Kolcun, Alexej (referee) ; Kolingerová, Ivana (advisor) Document type: Master’s theses
Year:
2007
Language:
cze Abstract:
[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.
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/9921