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)

Text
acmac-0116.pdf Download (699Kb) |

## Abstract

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 |

URI: | http://preprints.acmac.uoc.gr/id/eprint/116 |

### Actions (login required)

View Item |