Euclidean distance degree and mixed volume

2020/12/11 by Breiding, Paul, Sottile, Frank, Woodcock, James · 2 citations
#14M25 #90C26 #Algebraic Geometry (math.AG) #FOS: Mathematics

paper · doi:10.48550/arxiv.2012.06350

Abstract

We initiate a study of the Euclidean Distance Degree in the context of sparse polynomials. Specifically, we consider a hypersurface f=0 defined by a polynomial f that is general given its support, such that the support contains the origin. We show that the Euclidean Distance Degree of f=0 equals the mixed volume of the Newton polytopes of the associated Lagrange multiplier equations. We discuss the implication of our result for computational complexity and give a formula for the Euclidean distance degree when the Newton polytope is a rectangular parallelepiped.

Cited by

• The Critical Point Degree of a Periodic Graph
• Newton numbers, vanishing polytopes and algebraic degrees

Related

• Euclidean distance degree of complete intersections via Newton polytopes
• The algebraic degree of sparse polynomial optimization
• The Euclidean Distance Degree of Fermat Hypersurfaces
• The maximum likelihood degree of sparse polynomial systems
• Complexity of Sparse Polynomial Solving 2: Renormalization