A Method for Auto-Differentiation of the Voronoi Tessellation
Sergei Shumilin Alexander Ryabov Evgeny Burnaev Vladimir Vanovskii
Voronoi tessellation, also known as Voronoi diagram, is an important
computational geometry technique that has applications in various scientific
disciplines. It involves dividing a given space into regions based on the
proximity to a set of points. Autodifferentiation is a powerful tool for
solving optimization tasks. Autodifferentiation assumes constructing a
computational graph that allows to compute gradients using backpropagation
algorithm. However, often the Voronoi tessellation remains the only
non-differentiable part of a pipeline, prohibiting end-to-end differentiation.
We present the method for autodifferentiation of the 2D Voronoi tessellation.
The method allows one to construct the Voronoi tessellation and pass gradients,
making the construction end-to-end differentiable. We provide the
implementation details and present several important applications. To the best
of our knowledge this is the first autodifferentiable realization of the
Voronoi tessellation providing full set of Voronoi geometrical parameters in a
differentiable way.