Voronoi cells of varieties (Q820967): Difference between revisions

Consider a real algebraic variety \(X\) embedded in the Euclidean space \(\mathbb{R}^n\) with its Euclidean metric. For any smooth point \(y\in X\), let \(T_y X\) be the tangent space of \(X\) at \(y\) and consider the normal space \[ N_X(y) = \left\{u \in \mathbb{R}^n \ \vert\ u-y \text{~is orthogonal to~} T_yX\right\}. \] The Voronoi cell of the point \(y \in X\) is the subset \[ \text{Vor}_X(y) = \left\{u \in N_X(y)\ \middle\vert\ \|u-y\| = \min_{x\in X}\|u-x\|\right\}. \] The paper under review deals with the algebraic boundary of Voronoi cells, that is the Zariski closure of \(\partial\, \text{Vor}_X(y)\) in the complex affine space \(N_X(y)_{\mathbb{C}}\). Such algebraic boundary \(\partial_{\text{alg}} \text{Vor}_X(y)\) turns out to be a hypersurface and its degree is called Voronoi degree of \(X\) at \(y\). The authors describe a Gröbner-based algorithm to compute the ideal defining \(\partial_{\text{alg}} \text{Vor}_X(y)\) starting from the equations defining the variety \(X\) and the coordinates of the point \(y\). Focusing on the case of degree \(d\) hypersurfaces in \(\mathbb{R}^n\), the authors conjecture a formula for the Voronoi degree of a generic hypersurface (at any point) depending on the dimension \(n\) and the degree \(d\). They prove the formula for \(n \leq 3\). Moreover, the authors study the case of \(X\) being the variety of \(m\times n\) matrices of rank \(\leq r\). Using the Eckart-Young-Mirsky theorem, they give an explicit description of the Voronoi cell \(\text{Vor}_X(y)\) of a rank \(r\) matrix \(y\) in terms of the spectral norm.