Euclidean Distance Degree and Mixed Volume

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 equal...

Full description

Saved in:
Bibliographic Details
Published in:Foundations of computational mathematics 2022-12, Vol.22 (6), p.1743-1765
Main Authors: Breiding, P., Sottile, F., Woodcock, J.
Format: Article
Language:English
Subjects:
Applications of Mathematics
Computer Science
Economics
Euclidean geometry
Geometry, Plane
Geometry, Solid
Hyperspaces
Lagrange multiplier
Linear and Multilinear Algebras
Math Applications in Computer Science
Mathematical research
Mathematics
Mathematics and Statistics
Matrix Theory
Numerical Analysis
Parallelepipeds
Polynomials
Polytopes
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1615-3375
1615-3383
DOI:10.1007/s10208-021-09534-8