Bakalářská práce

Algoritmus pro konvexní obal v dimenzi 3

Algorithm for convex hull in dimension 3

Lívia Moncoľová
Anotace

Bakalářská práce se věnuje náhodnostnímu přírůstkovému algoritmu pro konvexní obal konečné množiny bodů v dimenzi 3. Podrobně popisuje všechny jeho procedury a zdůvodňuje jeho očekávanou časovou náročnost. V závěru se letmo zabývá dalším algoritmem pro konvexní obal založeném na principu rozděl a panuj.

Abstract

The thesis deals with a randomized incremental algorithm for the convex hull of a finite set of points in dimension 3. All the procedures are described in details. There is also a justification of the expected time. In the final part, the work touches another algorithm for the convex hull based on the so-called divide and conquer principle.

Klíčová slova
konvexní množina konvexní obal náhodnostní přírastkový algoritmus očekávaná časová náročnost konfigurační prostor convex set convex hull randomized incremental algorithm expected time configuration space
Zadání práce
Cílem práce je detailně popsat a zdůvodnit přírůstkový náhodnostní algoritmus pro nalezení konvexního obalu konečné množiny bodů v třírozměrném prostoru a aspoň částečně zdůvodnit jeho očekávanou časovou náročnost. Implementace algoritmu není součástí práce.
Administrativní informace
Práce zkontrolována:
12. 5. 2019 18:03, doc. RNDr. Martin Čadek, CSc., učo 233
Plný text práce
10,6 MB / soubor PDF
Jazyk práce
slovenština slovenština
Termín obhajoby
20. 6. 2019
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

Mgr. Mária Šimková, 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.
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.