Odhady počtu prázdných čtyřstěnů a ostatních simplexů

Abstract

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. 1

Let 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