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řírůstkového algoritmu. Dále 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 náhodnostní přírůstkový algoritmus nandomized incremental algorithm konfigurační prostor configuration space dvojitě souvislý seznam doubly-connected edge list polytop simplex triangulace triangulation 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:
17. 5. 2016 09:28, 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
22. 6. 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.