Decomposing a Random Newton Polygon
Consider a Newton polygon for a set of points in the plane with convex hull . The construction of the polygon is slightly different from the traditional one as follows (which is why some use the term Newton polytope).[more]
The point is associated with the monomial , and a set of points in the plane is associated with the polynomial , that is, the sum of the monomials corresponding to the points in the set. For example, is associated with . Note that coefficients do not matter.
A polynomial that can be factored into a product of polynomials of lower degree is called reducible. The Newton polygon of a reducible polynomial corresponds to the Minkowski sum of the Newton polygons of the factors of . If a Newton polygon corresponds to a reducible polynomial, then is called decomposable.
In this Demonstration, a random set of points is chosen inside the square of side length from 1 to 8. The program checks if the corresponding Newton polygon is decomposable or indecomposable by checking all possible decompositions based on the boundary of the polygon; in the latter case, the corresponding polynomial is irreducible over any field, that is, absolutely (or geometrically) irreducible.[less]
 S. Gao and A. G. B. Lauder, "Decomposition of Polytopes and Polynomials," Discrete and Computational Geometry, 26(1), 2001 pp. 89–104. doi:10.1007/s00454-001-0024-0.