  The mixed volume counts the roots of generic sparse polynomial systems. Mixed
cells are used to provide starting systems for homotopy algorithms that can
find all those roots, and track no unnecessary path. Up to now, algorithms for
that task were of enumerative type, with no general non- exponential complexity
bound. A geometric algorithm is introduced in this paper. Its complexity is
bounded in the average and probability-one settings in terms of some geometric
invariants: quermassintegrals associated to the tuple of convex hulls of the
support of each polynomial. Besides the complexity bounds, numerical results
are reported. Those are consistent with an output- sensitive running time for
each benchmark family where data is available. For some of those families, an
asymptotic running time gain over the best code available at this time was
noticed.
