Static and dynamic weighted Delaunay triangulations in the Euclidean plane and in the flat torus: properties, algorithms and applications

Delaunay triangulations and their extensions to weighted sets of points are considered here in the Euclidean space as well as in the flat torus, an infinite space obtained by repeating periodically a finite square box. In order to avoid unsafe redundancies, the generalization to the flat torus of two standard construction algorithm (namely, divide-and-conquer and flip) is made by using every particularity of this space, and this, without changing the time bounds of the original tools. (For the flip algorithm, it is still only a conjecture) In both spaces, the Delaunay triangulation is shown to minimize two functions over all triangulations of a given set of points: the circumscribing area and the dual measure. Finally, an algorithm is proposed to solve the problem of the motion of a weighted Delaunay triangulation due to the motion of its generating set. It is a simple and general tool with many applications in different fields.