An Output-sensitive Algorithm for Computing Projections of Resultant Polytopes

Emiris, Ioannis and Fisikopoulos, Vissarion and Konaxis, Christos and Penaranda, Luis (2012) An Output-sensitive Algorithm for Computing Projections of Resultant Polytopes. Symposium on Computational Geometry, SoCG 2012. (In Press)

[img] Text

Download (699Kb)
Official URL:


We develop an incremental algorithm to compute the Newton polytope of the resultant, aka resultant polytope, or its projection along a given direction. The resultant is fundamental in algebraic elimination and in implicitization of parametric hypersurfaces. Our algorithm exactly computes vertex- and halfspace-representations of the desired polytope using an oracle producing resultant vertices in a given direction. It is output-sensitive as it uses one oracle call per vertex. We overcome the bottleneck of determinantal predicates by hashing, thus accelerating execution from $18$ to $100$ times. We implement our algorithm using the experimental CGAL package {\tt triangulation}. A variant of the algorithm computes successively tighter inner and outer approximations: when these polytopes have, respectively, 90\% and 105\% of the true volume, runtime is reduced up to $25$ times. Our method computes instances of $5$-, $6$- or $7$-dimensional polytopes with $35$K, $23$K or $500$ vertices, resp., within $2$hr. Compared to tropical geometry software, ours is faster up to dimension $5$ or $6$, and competitive in higher dimensions.

Item Type: Article
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA76 Computer software
Depositing User: Christos Konaxis
Date Deposited: 30 Jun 2012 13:15
Last Modified: 05 May 2017 23:41

Actions (login required)

View Item View Item