Diplomová práce

Diagramy Voronoia pro neeuklidovské metriky

Voronoi diagrams for noneuclidean metrics

Bc. Michal Novák
Anotace

Tato diplomová práce popisuje algoritmus rozděl a panuj konstruující diagram Voronoia pro množinu bodů zadanou v rovině. Tento algoritmus si uvedeme spolu s důkazy korektnosti a časové náročnosti, přičemž funkčnost algoritmu omezíme na L_p metriky pro p mezi jednou a nekonečnem. Pro metriky L_1 a L_inf naznačíme rozšíření algoritmu nutné pro zachování korektního výstupu. Uvedeme též výčet alternativních …více

Abstract

This master's thesis describes divide and conquer algorithm which constructs Voronoi diagram for an arbitrary set of points in a plane. We introduce this algorithm for metrics L_p for p between one and infinity in chapters one to three with suitable proofs of correctness and time complexity. Then we outline extension of this algorithm for p equals one or infinity. A list of other algorithms dealing …více

Klíčová slova
Diagramy Voronoia Neeuklidovské metriky Rozděl a panuj Geometrické algoritmy Voronoi diagrams Noneuclidean metrics Divide and conquer Geometric algorithms
Zadání práce
V rovině je zadána nějaká obecně neeuklidovská metrika. Diagram Voronoia pro tuto metriku a konečnou množinu P bodů v rovině je rozdělení roviny na oblasti kolem bodů množiny P takové, že zadaný bod v oblasti je nejbližším bodem z množiny P pro všechny body této oblasti. Algoritmické řešení této úlohy je jednou ze základních úloh počítačové geometrie. Diplomová práce by měla být přehledem výsledků a používaných metod především pro metriky L_p, kde p je číslo mezi 1 a nekonečnem. Zmíněny by měly být i jejich aplikace. Některý algoritmus pro některou z těchto metrik by měl student implementovat.
Administrativní informace
Práce zkontrolována:
12. 5. 2019 18:54, doc. RNDr. Martin Čadek, CSc., učo 233
Plný text práce
1,6 MB / soubor PDF
Přílohy (1)
Jazyk práce
čeština čeština
Termín obhajoby
11. 2. 2020
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

doc. Mgr. Josef Šilhan, Ph.D., učo 3980
Ú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.