next up previous contents
Next: Static lifting Up: MVC: four lifting Previous: MVC: four lifting

Implicit lifting

Mixed volumes relate the volume of a polytope to the surface area of its faces. This becomes apparent by the following recursive formula to compute the mixed volume of a tuple of polytopes :

 

where ranges over all normals on facets spanned by edges of the polytopes . The function is the support function of . U is a unimodular transformation (), with first row equal to , so that the arguments of live in -dimensional space. By we denote the face of P, of those points in P for which the value of the support function is attained.

Bernshtein's proposed to use the homotopy

 

where c is the constant term of the first polynomial . Applying (12) to a system with randomly chosen complex coefficients, Bernshtein proved that all isolated solutions of can be obtained. This solver runs in an analogue recursive way as formula (11).

Because formule (11) deals with the original polytope configuration, we can get an indication whether the polytopes are in generic position, i.e.: if for any direction , there exists a component i, so that is a vertex. The vectors computed in the elaboration of (11) provide potential candidates showing that the system is not in generic position.

We now call this method implicit lifting, as a special instance of a lifting method to compute mixed volumes, a method we explain next.



Jan Verschelde
Thu Nov 21 10:50:01 MET 1996