Polytopes defined by oracles: algorithms and combinatorics

Vissarion Fisikopoulos

University of Athens, Greece

University of Athens, Greece

2014/06/23 Monday 4PM-5PM

Room 1409

Room 1409

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.

Tags: VissarionFisikopoulos