Huber and Sturmfels developed in [12] a lifting method for computing mixed subdivisions and mixed volumes. We call it static lifting to make the distinction with dynamic lifting. Static lifting means that first all points are lifted, followed by the computation of the lower hull. We illustrate the idea in Figure 5.
Figure 5: The construction of a regular triangulation by lifting.
In our implementation, the user can choose between three different types of lifting functions: linear, polynomial or point-wise. Linear lifting preserves the face structure of the polytopes. Polynomial functions can be supplied by the user, or the target system can be used. By point-wise lifting we can obtain any general assignment of lifting values to the points. Either the user can give the values or let a random number generator perform the lifting. Currently the transition form integer to floating-point lifting functions is being implemented.
Mixed subdivisions can be seen as generalizations of subdivisions for computing mixed volumes. The definition in [12] allows to take advantage of repeated polytopes. Huber and Sturmfels provided an alternative constructive proof of Bernshtein's theorem, introducing the so-called polyhedral homotopies, to solve systems with randomly chosen coefficients. We explain the incremental polyhedral homotopy continuation in the next section.