Diplomová práce

Geometrické algoritmy v dimenzi 3

Geometric algorithms in dimension 3

Ing. Bc. Dušan Medla
Anotace

Tato práce studuje geometrické algoritmy v dimenzi 3. V první kapitole se zabýváme konvexními obaly. Hlavní část kapitoly tvoří podrobný popis náhodnostního přírustkového algoritmu. Dale je studován konfigurační prostor, který pak umožňuje odhadnout očekávanou dobu běhu algoritmu. Ve druhé kapitole studujeme triangulaci. Je zaveden potřebný teoretický aparát pro definici v obecné dimenzi. Dále je studováno omezení počtu tetrahedronů. Poté je uveden algoritmus pro 3-triangulaci.

Abstract

This thesis deals with geometric algorithms in dimension 3. In the first chapter we investigate convex hull. The main part of the chapter consists of the detail description of a randomized incremental algorithm. Next we deal with the notion of configuration space which helps us to determine the expected time of the algorithm. The second chapter concerns triangulations. We establish needed notions and …více

Klíčová slova
Konvexní obal Convex hull Algoritmus Algorithm Komplex Complex Triangulace Triangulation Konfigurační prostor Configuration space Simplex Tetrahedronizace Tetrahedronization
Zadání práce
Cílem práce je podrobně popsat algoritmy pro řešení některých geometrických úloh v dimenzích 3. Výběr úloh by mohl zahrnovat konvexní obaly, triangulaci v prostoru, ale i jiné podle doporučené literatury nebo zájmů studenta.
Administrativní informace
Práce zkontrolována:
7. 4. 2015 10:01, doc. RNDr. Martin Čadek, CSc., učo 233
Plný text práce
628,6 KB / soubor PDF
Jazyk práce
čeština čeština
Termín obhajoby
17. 2. 2016
Práce nebyla obhájena

Vedoucí

doc. RNDr. Martin Čadek, CSc., učo 233
ÚMS Ústavy PřF MU

Oponent

Mgr. Martin Panák, Ph.D.
ÚMS Ústavy PřF MU

Literatura

  • DE BERG, Mark; Otfried CHEONG; Marc VAN KREVELD a Mark OVERMARS. Computational geometry. 3rd ed. Berlin, Heidelberg: Springer, 2008. ISBN 978-3-540-77973-5.
  • KLEE, V. On the complexity of d-dimensional Voronoi diagram. Archiv der Mathematik. 1980, roč. 34(1980), s. 75-80.
  • SEIDEL, R. Small-dimensional linear programming and convex hulls made easy. Discrete Comput. Geom. 1991, roč. 6(1991), s. 423-434.
Citovat tuto práci
Masarykova univerzita Přírodovědecká fakulta
Studijní program
Matematika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.