Euclidean Distance Degree and Mixed Volume Academic Article uri icon


  • AbstractWe initiate a study of the Euclidean distance degree in the context of sparse polynomials. Specifically, we consider a hypersurface $$f=0$$ f = 0 defined by a polynomialf that is general given its support, such that the support contains the origin. We show that the Euclidean distance degree of $$f=0$$ 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.

published proceedings

  • Foundations of Computational Mathematics

author list (cited authors)

  • Breiding, P., Sottile, F., & Woodcock, J.

complete list of authors

  • Breiding, P||Sottile, F||Woodcock, J

publication date

  • September 2021