Euclidean distance degree and mixed volume
This pretty paper studies a special case of the algebraic Euclidean distance problem: given a polynomial \(f\in \mathbb{C} [x_1, \ldots , x_n]\) and a generic point \((u_1, \ldots , u_n) \in \mathbb{C}^n,\) determine the number of critical points of the function that computes squared Euclidean distance from \(u\) to the hypersurface \(V(f).\) Here, ``Euclidean distance function refers to the complexified distance on \(\mathbb{R}^n,\) rather than the Hermitian distance, so this function is given by \begin{align*} d_u : V(f) &\to \mathbb{C} \\ (x_1, \ldots , x_n) &\mapsto (x_1-u_1)^2 + \cdots + (x_n - u_n)^2. \end{align*} The number of such critical points is known as the Euclidean distance degree of \(V(f),\) and denoted \(\operatorname{EDD} (f)\) by the authors. When \(f\) is generic in the space of all degree-\(d\) polynomials, it is well-known from prior work that \[ \operatorname{EDD} (f) = d \, \displaystyle\sum_{i=0}^{n-1} (d-1)^i. \] The authors' main result is a refinement of this formula to the case where \(f\) is generic in the space of all polynomials with a fixed monomial support set \(\mathcal{A} \subset \mathbb{Z}_{\ge 0}^{n}\) that contains the origin (ie, \(f\) has a nonzero constant term.) They prove that \(\operatorname{EDD} (V(f)) = \operatorname{MV} (P, P_1, \ldots , P_n),\) where \begin{itemize} \item[(1)] \(P = \operatorname{conv} (\mathcal{A})\) is the Newton polytope of \(f\), \item[(2)] \(P_1, \ldots , P_n\) are the Newton polytopes of certain Lagrange multiplier equations whose supports are governed by \(\mathcal{A},\) and \item[(3)] \(\operatorname{MV}\) denotes the mixed volume. \end{itemize} They conclude by evaluating their formula when \(P\) is a rectangular parallelepiped. The result, in some sense, is ``expected due to a celebrated theorem of Bernstein. However, the conclusion is non-trivial: for \(f\) that \textit{do not} satisfy certain genericity conditions, we may have a strict inequality \(\operatorname{EDD} (V(f)) < \operatorname{MV} (P, P_1, \ldots , P_n)\). These genericity conditions turn out to be the main tool used in the proof. If the inequality is strict, then Bernstein's ``other theorem states that a solution must exist to some \textit{facial system} associated to the Lagrangian equations. When \(f\) is sufficiently generic, the authors prove these facial systems have no solutions.
- A new decision method for elementary algebra
- A Polyhedral Method for Solving Sparse Polynomial Systems
- Algorithm 795
- Algorithm 921: alphaCertified: certifying solutions to polynomial systems
- Certifying approximate solutions to polynomial systems on Macaulay2
- Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
- Computing mixed volume and all mixed cells in quermassintegral time
- Convex Polytopes, Algebraic Geometry, and Combinatorics
- Euclidean distance degree of the multiview variety
- Finding at least one point in each connected component of a real algebraic set defined by a single equation
- Galois theory for general systems of polynomial equations
- Generic properties of dispersion relations for discrete periodic operators
- HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method
- HomotopyContinuation.jl: a package for homotopy continuation in Julia
- scientific article; zbMATH DE number 52497 (Why is no real title available?)
- scientific article; zbMATH DE number 3550860 (Why is no real title available?)
- scientific article; zbMATH DE number 1440908 (Why is no real title available?)
- scientific article; zbMATH DE number 960150 (Why is no real title available?)
- Mixed volume techniques for embeddings of Laman graphs
- Numerically computing real points on algebraic sets
- On the combinatorial and algebraic complexity of quantifier elimination
- Polyedres de Newton et nombres de Milnor
- Real solving for positive dimensional systems.
- The Euclidean distance degree of an algebraic variety
- The Euclidean distance degree of smooth complex projective varieties
- The number of roots of a system of equations
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- The Euclidean distance degree of smooth complex projective varieties
- The distance function from a real algebraic variety
- Asymptotics of degrees and ED degrees of Segre products
- Topological methods in applied algebraic geometry and algebraic statistics
- Euclidean distance degree of projective varieties
- Polar degrees and closest points in codimension two
- The Maximum Likelihood Degree of Sparse Polynomial Systems
- On the polyhedral homotopy method for solving generalized Nash equilibrium problems of polynomials
- Critical points of discrete periodic operators
- Euclidean distance degree in manifold optimization
- Algebraic degree of optimization over a variety with an application to P-norm distance degree
- Moment varieties from inverse Gaussian and gamma distributions
Uses Software
This page was built for publication: Euclidean distance degree and mixed volume
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2098233)
