KAIST Discrete Math Seminar

We develop a new paradigm to construct polytopes whose vertices can be obtained by an effective oracle in a unique fashion. Our main motivation comes from computational algebraic geometry. From this perspective these polytopes, called resultant polytopes, characterize polynomials better than total degree thus offering the fundamental representation in sparse elimination theory. We propose an output-sensitive algorithm that requires the minimum number of oracle calls, each reducing to the construction of a regular triangulation of the input set of points. Its implementation has been proven, among others, a valuable computational tool in our study of the combinatorial characterization of 4-dimensional resultant polytopes. We present the results of this study, that is, upper and lower bounds on the number of faces of 4-dimensional resultant polytopes.