Tato diplomová práce se zabývá teorií potřebnou pro studium zobecněných Voroneho
diagramů. Nejprve se zaměřuje na Obecný Voroneho diagram, pro který stručně uvede jeho definice a vlastnosti. Dále pro tento diagram popíše tři různé algoritmy, konkrétně Inkrementální algoritmus, "Plane sweep" algoritmus a Metodu rostoucích regionů. Posléze se zaměří na zobecněné Voroneho diagramy, a to na Voroneho diagram v L1 metrice, Voroneho diagram kružnic a Laguerre Voroneho diagram. Pro každý z těchto diagramů zpracuje teorii a minimálně jeden ze zmíněných algoritmů. Součástí práce je implementace Inkrementálního algoritmu pro Laguerre Voroneho diagram v programu Mathematica 7.
Annotation in English
The thesis deals with the theory needed for studying generalized Voronoi diagrams. At the beginning it focuses on the Ordinary Voronoi diagram and briefly introduces its definition and characteristics. After that three different algorithms for this diagram are described, specifically Incremental algorithm, ?Plane sweep? algorithm and the Method of growing regions. Then it concentrates on generalized Voronoi diagrams, which are Voronoi diaram in L1 distance, Voronoi diagram of circle and Laguerre Voronoi diagram.
For each of these diagrams a theory and at least one of the algorithms are processed. One part of the thesis is the implementation of Incremental algorithm for Laguerre Voronoi diagram in software Mathematica 7.
Ordinary Voronoi diagram, Voronoi diagram in L1 distance, Voronoi diagram of circle, Laguerre Voronoi diagram, Incremental algorithm, ?Plane sweep? algorithm, Method of growing regions
Length of the covering note
86 s.
Language
CZ
Annotation
Tato diplomová práce se zabývá teorií potřebnou pro studium zobecněných Voroneho
diagramů. Nejprve se zaměřuje na Obecný Voroneho diagram, pro který stručně uvede jeho definice a vlastnosti. Dále pro tento diagram popíše tři různé algoritmy, konkrétně Inkrementální algoritmus, "Plane sweep" algoritmus a Metodu rostoucích regionů. Posléze se zaměří na zobecněné Voroneho diagramy, a to na Voroneho diagram v L1 metrice, Voroneho diagram kružnic a Laguerre Voroneho diagram. Pro každý z těchto diagramů zpracuje teorii a minimálně jeden ze zmíněných algoritmů. Součástí práce je implementace Inkrementálního algoritmu pro Laguerre Voroneho diagram v programu Mathematica 7.
Annotation in English
The thesis deals with the theory needed for studying generalized Voronoi diagrams. At the beginning it focuses on the Ordinary Voronoi diagram and briefly introduces its definition and characteristics. After that three different algorithms for this diagram are described, specifically Incremental algorithm, ?Plane sweep? algorithm and the Method of growing regions. Then it concentrates on generalized Voronoi diagrams, which are Voronoi diaram in L1 distance, Voronoi diagram of circle and Laguerre Voronoi diagram.
For each of these diagrams a theory and at least one of the algorithms are processed. One part of the thesis is the implementation of Incremental algorithm for Laguerre Voronoi diagram in software Mathematica 7.
Ordinary Voronoi diagram, Voronoi diagram in L1 distance, Voronoi diagram of circle, Laguerre Voronoi diagram, Incremental algorithm, ?Plane sweep? algorithm, Method of growing regions
Research Plan
Zpracujte teorii potřebnou pro studium zobecněných Voroneho diagramů.
Pro vybrané typy zobecnění (např. změna metriky, vážené Voroneho diagramy apod.) uveďte vhodné algoritmy popř. modifikujte známé algoritmy a uveďte výhody a nevýhody jejich použití.
Ve vhodném software proveďte implementaci vybraných algoritmů.
Uveďte aplikace a praktické využití uvedených zobecnění.
Research Plan
Zpracujte teorii potřebnou pro studium zobecněných Voroneho diagramů.
Pro vybrané typy zobecnění (např. změna metriky, vážené Voroneho diagramy apod.) uveďte vhodné algoritmy popř. modifikujte známé algoritmy a uveďte výhody a nevýhody jejich použití.
Ve vhodném software proveďte implementaci vybraných algoritmů.
Uveďte aplikace a praktické využití uvedených zobecnění.
Recommended resources
Li Jin, Donguk Kim, Lisen Mu, Deok-Soo Kim, Shi-Min Hu: A sweepline algorithm for Euclidean Voronoi diagram of circles. Computer-Aided Design 38. 2006
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computation Geometry. Algorithms and Applications. Berlin. Springer Verlag. 1997
Časopisecké zdroje
Recommended resources
Li Jin, Donguk Kim, Lisen Mu, Deok-Soo Kim, Shi-Min Hu: A sweepline algorithm for Euclidean Voronoi diagram of circles. Computer-Aided Design 38. 2006
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computation Geometry. Algorithms and Applications. Berlin. Springer Verlag. 1997