Bachelor's Thesis

Application of Voronoi diagrams in theoretical chemistry

Final Thesis 1.53 MB Appendix 5.49 MB

Author of thesis: Pavel Kozák

Acad. year: 2025/2026

Supervisor: Mgr. Jan Pavlík, Ph.D.

Reviewer: doc. Mgr. Jaroslav Hrdina, Ph.D.

Abstract:

This bachelor’s thesis focuses on Voronoi diagrams in Euclidean spaces, their extension to weighted Voronoi diagrams by modifying the metric, and their potential application to a problem in theoretical chemistry. The properties of both standard and weighted Voronoi diagrams are explored. Selected algorithms for computing Voronoi diagrams in 2D and 3D are compared. This is followed by the derivation of a custom algorithm suitable for solving the given task. Finally, the approach using Voronoi diagrams and selected metrics is applied to a test data sample, along with a commentary on the results.

Keywords:

Metric spaces, convex sets, Voronoi diagram, Delaunay triangulation, weighted Voronoi diagram, algorithms for obtaining single Voronoi cell.

Date of defence

09.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaBznamka

Grading

B

Process of defence

Student prezentoval svou práci, byly přečeteny posudky vedoucího a oponenta. Otázky oponenta: 1. Ano, stačil. 2. Rychlé vysvětlení 3. Vysvětlena situace v prostoru, v čem fungují či spíše nefungují postupy z roviny a jak se to tedy řeší 4. Vysvětlení uvedené definice. Byla napsána lepší správná verze původní definice. dr. Trnka: diskuze nad některými větami a tím, čemu se práce věnovala a čemu ne.

Language of thesis

Czech

Faculty

Department

Study programme

Mathematical Engineering (B-MAI-P)

Composition of Committee

prof. RNDr. Miroslav Doupovec, CSc., dr. h. c. (předseda)
doc. Mgr. Jaroslav Hrdina, Ph.D. (místopředseda)
Mgr. Dominik Trnka, Ph.D. (člen)
doc. Ing. Petr Tomášek, Ph.D. (člen)
doc. RNDr. Libor Žák, Ph.D. (člen)

Supervisor’s report
Mgr. Jan Pavlík, Ph.D.

Práce je věnována studiu Voroného diagramů (VD), jejich modifikací a metodám výpočtu a přihlédnutím k aplikaci v teoretické chemii. Student se věnoval VD v euklidovském prostoru a vedle základního pojetí se zabýval konstrukcí jedné konkrétní buňky. Metoda, ač složitostně netestována (posuzování složitosti algoritmu nebylo předmětem práce), se jeví jako užitečný nástroj pro nalezení buňky pro jeden prvek bez nutnosti počítat buňky ostatní.

Ladění algoritmu v R^3 a jeho implementaci v Pythonu věnoval student značné množství času. Mimo to, na základě školitelem vzneseného návrhu vyvinul metodu, kde využitím VD by bylo možno získat obor možné extrapolace hodnot. Následně vypočítal VD pro data získaná metadami výpočtů v teoretické chemii a snažil se na nich ověřit užitečnost pro výpočet odhadu veličiny chemický posun. Přestože jsou výstupy z algoritmu v mnoha případech zcela odlišné od požadovaných hodnot, na základě vyjádření ze strany chemických poptávačů metody je možné výsledky stále intrpretovat způsobem, jenž metodu neodsuzuje k zániku, nýbrž k úpravě vedoucí k vyladění. Jednou z takových úprav může být zapojení vážených VD, kterým je věnována část 3. kapitoly této práce.

Grade proposed by supervisor: B

Práce obsahuje mírně větší počet překlepů. Poměrně často se mění označení dimenze, střídavě jsou to indexy "n" a "d". V některých chvílích to vytváří matoucí text. Příklad 2.1.3., Příklad 2.1.5, Příklad 2.1.12 , Definice 2.3.1. Z těchto důvodu je Definice 2.2.9 nepochopitelná.  Na několika místech je špatně použití symbolů "patří" a "je prvkem", Definice 3.1.1, Věta 3.1.7. V Definici 2.2.1 je jiné označení intervalu než ve zbytku textu. Dále v textu jsou  nějaké další podobné nepřesnosti které neuvádím. 

V definici 2.2.3 chybí podmínka že součet lambd musí být jedna. Ve větě 2.2.6 je potřeba dodat že "všech podprostorů"

Nejsou zohledněny limitní případy, zejména ve větě 3.1.7 která je klíčová, je v důkazu předpoklad existence vrcholu W, jehož existence ale závisí na počtu řídících bodů. 

Kapitola 4.5.1 obsahuje nedefinované objekty, R_Q, r, Q_l..  

Nerozumím tomu proč jsou kódy formou přílohy a ne online, například na Githubu. Je škoda, že se vyvinutý algoritmus nepoužije i v aplikaci. Je pěkné, že teoretické výsledky slouží k důkazu korektnosti algoritmu, ale je škoda že se takto vyvinutý algoritmus nepoužije na analýzu proteinů. Chápu ale že to je nad rámec formátu BP a nepovažuji to za nedostatek.

Celkově na mně práce působí velmi dobře, obsahuje vlastní teoretické výsledky (Věta 3.1.7), vlastní návrh algoritmu (kap. 4.5.2), vlastní implementaci v Pythonu (přílohy) a originální aplikaci (kap. 5). Hlavním benefitem práce je právě komplexní přístup k problému. Topics for thesis defence:
  1. Proč v algoritmu 4.4 pracujete v rovině vložené v prostoru? Pokud je to kvůli orientaci nestačil by determinant?
  2. Vysvětlete Definici 2.2.9.
  3. Vysvětlete pojmy kapitoly 4.5.1
  4. U orientace vrcholu stěny (str. 24), proč záporná hdonota souvisí z orientaci CW (čekal bych to naopak)

Grade proposed by reviewer: B

Responsibility: Mgr. et Mgr. Hana Odstrčilová