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.
- A certificate for semidefinite relaxations in computing positive-dimensional real radical ideals
- A generalization of the Eckart-Young-Mirsky matrix approximation theorem
- scientific article; zbMATH DE number 421675 (Why is no real title available?)
- scientific article; zbMATH DE number 3859276 (Why is no real title available?)
- scientific article; zbMATH DE number 3235051 (Why is no real title available?)
- Introduction to Toric Varieties. (AM-131)
- Learning algebraic varieties from samples
- Offset hypersurfaces and persistent homology of algebraic varieties
- On the geometry of the set of symmetric matrices with repeated eigenvalues
- On the local stability of semidefinite relaxations
- Random points on an algebraic manifold
- The bottleneck degree of algebraic varieties
- The distance function from a real algebraic variety
- The Euclidean distance degree of an algebraic variety
- Voronoi-like partition of lattice in cellular automata
- Logarithmic Voronoi cells
- Voronoi tessellations associated to the Cremona group
- Voronoi diagrams of algebraic varieties under polyhedral norms
- Logarithmic Voronoi cells for Gaussian models
- Logarithmic Voronoi polytopes for discrete linear models
- Voronoi cells in metric algebraic geometry of plane curves
- Osculating geometry and higher-order distance loci
- MFO-RIMS tandem workshop: Optimization, theoretical computer science and algebraic geometry: convexity and beyond. Abstracts from the MFO-RIMS tandem workshop held February 16--21, 2025
- Conditional Euclidean distance optimization via relative tangency
- Polyhedral Voronoi cells
This page was built for publication: Voronoi cells of varieties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820967)
