Computations of Laguerre tessellations with given cell volumes

Abstract

Given a finite set of pairs in Rd ×R, nuclei and weights, Laguerre tessellations allow us to subdivide Euclidean space Rd into finitely many polyhedral cells using the power dis- tance. We are interested in the problem of finding weights so that the Laguerre cells have prescribed volumes and nuclei. Our primary aim is to present the theoretical background leading to the problem's solution. Here we complete some proofs that are shortened in the literature, while other theorems are cited. Then, we demonstrate two own computer programs and the corresponding numerical results. First, we compute the desired set of weights that generates the Laguerre tessellation with prescribed cell volumes and apply it to a unit cube in R3 . The application of this method relies on the Barzilai-Borwein gradient descent and Voro++ library, which computes the volumes of cells in each itera- tion. Furthermore, an iterative approach approximates a centroidal Laguerre tessellation, where the nuclei coincide with the centroids of Laguerre cells. 1

Máme-li konečnou množinu dvojic v Rd ×R, generátorů a vah, tak nám Laguerrovy mo- zaiky umožňují rozdělit Euklidovský prostor Rd na konečně mnoho polyedrických buněk pomocí mocenské vzdálenosti. Zajímá nás problém nalezení takových vah, že Laguerrovy buňky mají předepsané objemy a generátory. Naším základním cílem je představit teo- retický podklad vedoucí k řešení daného problému. V textu dokončíme některé důkazy, které jsou v literatuře zkráceny, zatímco ostatní věty jsou citovány. Poté předvedeme dva vlastní počítačové programy a odpovídající numerické výsledky. Nejprve spočítáme poža- dovanou sadu vah, která vygeneruje Laguerrovu mozaiku s předepsanými objemy buněk a aplikujeme ji na jednotkovou krychli v R3 . Aplikace této metody se opírá o Barzilai- Borweinův gradientní sestup a knihovnu Voro++, která počítá objemy buněk v každé iteraci. Iterativní přístup dále vede k aproximaci centroidální Laguerrovy mozaiky, kde se navíc generátory shodují s těžišti buněk. 1