Newton Polytopes and Witness Sets

We present two algorithms that compute the Newton polytope of a polynomial f defining a hypersurface H in ℂn using numerical computation. The first algorithm assumes that we may only compute values of f-this may occur if f is given as a straight-line program, as a determinant, or as an oracle. The second algorithm assumes that H is represented numerically via a witness set. That is, it computes the Newton polytope of H using only the ability to compute numerical representatives of its intersections with lines. Such witness set representations are readily obtained when H is the image of a map or is a discriminant. We use the second algorithm to compute a face of the Newton polytope of the Lüroth invariant, as well as its restriction to that face. © 2014 Springer Basel.