## triangulation

swMATH ID: | 10357 |

Software Authors: | Emiris, Ioannis Z.; Fisikopoulos, Vissarion; Konaxis, Christos; Peñaranda, Luis |

Description: | An oracle-based, output-sensitive algorithm for projections of resultant polytopes. We design an algorithm to compute the Newton polytope of the resultant, known as resultant polytope, or its orthogonal projection along a given direction. The resultant is fundamental in algebraic elimination, optimization, and geometric modeling. Our algorithm exactly computes vertex- and halfspace-representations of the polytope using an oracle producing resultant vertices in a given direction, thus avoiding walking on the polytope whose dimension is α-n-1, where the input consists of α points in ℤ n . Our approach is output-sensitive as it makes one oracle call per vertex and per facet. It extends to any polytope whose oracle-based definition is advantageous, such as the secondary and discriminant polytopes. Our publicly available implementation uses the experimental CGAL package triangulation. Our method computes 5-, 6- and 7- dimensional polytopes with 35K, 23K and 500 vertices, respectively, within 2hrs, and the Newton polytopes of many important surface equations encountered in geometric modeling in <1sec, whereas the corresponding secondary polytopes are intractable. It is faster than tropical geometry software up to dimension 5 or 6. Hashing determinantal predicates accelerates execution up to 100 times. One variant computes inner and outer approximations with, respectively, 90 |

Homepage: | http://doc.cgal.org/latest/Triangulation_2/classCGAL_1_1Delaunay__triangulation__2.html |

Dependencies: | CGAL |

Keywords: | general dimension; convex hull; regular triangulation; secondary polytope; resultant; CGAL implementation; experimental complexity |

Related Software: | respol; TOPCOM; CGAL; NumericalNP; Bertini.m2; Bertini; SageMath; Macaulay2; Resultants; Maple; Hull; Eigen; polymake; LinBox; iB4e; TropLi |

Cited in: | 5 Publications |

all
top 5

### Cited by 7 Authors

3 | Emiris, Ioannis Z. |

3 | Fisikopoulos, Vissarion |

2 | Konaxis, Christos |

2 | Peñaranda, Luis Mariano |

1 | Brysiewicz, Taylor |

1 | Gärtner, Bernd |

1 | Laroche, Clément |

### Cited in 5 Serials

1 | Computer Aided Geometric Design |

1 | Journal of Symbolic Computation |

1 | International Journal of Computational Geometry & Applications |

1 | Computational Geometry |

1 | Mathematics in Computer Science |

### Cited in 4 Fields

3 | Numerical analysis (65-XX) |

2 | Computer science (68-XX) |

1 | Algebraic geometry (14-XX) |

1 | Convex and discrete geometry (52-XX) |