Original title:
Odhady počtu prázdných čtyřstěnů a ostatních simplexů
Translated title:
Bounds of number of empty tetrahedra and other simplices
Authors:
Reichel, Tomáš ; Valtr, Pavel (advisor) ; Balko, Martin (referee) Document type: Master’s theses
Year:
2020
Language:
cze Abstract:
[cze][eng] Mějme v jednotkové krychli konečnou množinu M uniformně náhodně zvolených bodů. Každá čtveřice bodů z M má jakožto čtyřstěn buď uvnitř nějaký bod z množiny M, nebo je prázdná. V této práci předvedeme horní odhad střední hodnoty počtu těchto prázdných čtyřstěnů vzhledem k velikosti množiny M a ukážeme, jak je odhad nejspíše vzdálen od aproximace střední hodnoty, kterou necháme přímočarým algoritmem spočí- tat počítač. Nakonec pak opustíme trojrozměrný případ a budeme se věnovat obecnější úloze v libovolné dimenzi d, kde namísto prázdných čtyřstěnů v krychli budou figurovat prázdné d-simplexy v d-dimenzionální krychli. Horní odhad pro d-dimenzionální případ pak porovnáme s výsledky z jiného článku o stejném tématu. 1Let M be a finite set of random uniformly distributed points lying in a unit cube. Every four points from M make a tetrahedron and the tetrahedron can either contain some of the other points from M, or it can be empty. This diploma thesis brings an upper bound of the expected value of the number of empty tetrahedra with respect to size of M. We also show how precise is the upper bound in comparison to an approximation computed by a straightforward algorithm. In the last section we move from the three- dimensional case to a general dimension d. In the general d-dimensional case we have empty d-simplices in a d-hypercube instead of empty tetrahedra in a cube. Then we compare the upper bound for d-dimensional case to the results from another paper on this topic. 1
Keywords:
bound; empty simplices; empty tetrahedra; Euclidean space; point sets; random point sets; euklidovský prostor; množiny bodů; náhodné množiny bodů; odhad; prázdné simplexy; prázdné čtyřstěny
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/121153