Consider a polynomial with for all , where its Newton polytope is defined as the convex hull of vectors .
Now consider the `scattering map’ where for all . We claim that is an one-to-one map between and the interior of .
Firstly, suppose the matrix does not have full rank, i.e. there exists such that for all . In this case, Therefore, one can project by setting some so that there’s no more vector such that for all . Conversely, one can recover the original image by solving these equations . Therefore, we can assume that the matrix has full rank, then .
Next we show that interior points of are in the .
Let be a interior point in defined by where and . Equations are where Let , and then so we only need to show that has saddle points in because for all .
To see it, we firstly notice that is a strict convex function of . In fact, the Hessian of is For any , It cannot vanish because that it only happens when for all , but we have assumed has full rank.
For a strict convex function on , it has a unique minimal in iff it does not take its minimal when goes to infinity along any direction. In our case, we only need that for any and , there exist some such that and if , there exist some such that the exponentials are all negative, then when .
In fact, if , for a given , the hyperplain with normal vector crossing divides the space into semi-spaces and , then in are what we are looking for. Conversely, if , one can find a hyperplain such that , then the normal vector of gives the wanted direction. These are direct results of convexity of .
Therefore, we have proven that has a unique minimal in when and no minimal in when . Hence, is an one-to-one map between and the interior of .
Generally, let be a interior point in Minkowski sum corresponding to defined by where and . Equations are where Write we only need to show that has a unique saddle point in .
We assume that for all . Here, is no longer a strict convex function. However, take a positive number such that for all , consider a new function since are convex functions and , are convex functions, so is their product. Since has the same minimums as , so we can further assume that for all .
Finally, we claim that does not take minimum when goes to infinity along any direction. It is because that for a given and each , when , so does . Therefore, equation has a unique solution.