Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, July 12, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Vissarion Fisikopoulos (National and Kapodistrian University of Athens)
We develop a new paradigm to construct polytopes whose vertices can be obtained by an effective oracle in a unique fashion. Starting with the Newton polytope of the resultant, our method also efficiently computes secondary polytopes as well as the Newton polytope of the discriminant. We propose an output-sensitive algorithm that requires the minimum number of oracles, each reducing to the construction of a regular triangulation of the input pointset. The C++ implementation of this algorithm has allowed us to compute resultant polytopes in 7 or 8 dimensions. It has also yielded the most complex 3d and 4d resultant polytopes, the latter with f-vector (22,66,66,22,1), thus opening the study of this polytope family. Finally, we discuss open algorithmic problems regarding such polytopes.
Automatic MiSe System Software Version 1.4803M | admin login