An oracle-based, output-sensitive algorithm for projections of resultant polytopes

DOI10.1142/S0218195913600108MaRDI QIDQ2875648zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ioannis Z. Emiris, Vissarion Fisikopoulos, Christos Konaxis, Luis Peñaranda

Publication date 11 August 2014

Published in International Journal of Computational Geometry \& Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.5985

zbMATH Keywords

CGAL implementationconvex hullexperimental complexitygeneral dimensionregular triangulationresultantsecondary polytope

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 alpha-n-1, where the input consists of alpha points in Z^n. Our approach is output-sensitive as it makes one oracle call per vertex and 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% and 105% of the true volume, up to 25 times faster.

Recommendations

• An output-sensitive algorithm for computing projections of resultant polytopes
• scientific article; zbMATH DE number 3945874
• An iteration method of constructing orthogonal projections of convex polyhedral sets
• Oracle-polynomial-time approximation of largest simplices in convex bodies
• An Exact Algorithm for Projection onto a Polyhedral Cone
• Projection algorithms: Results and open problems
• Solution of projection problems over polytopes
• An output sensitive algorithm for discrete convex hulls
• An algorithm for projecting onto simplicial cones

Cites work

• A characterization of A-discriminantal hypersurfaces in terms of logarithmic Gauss map
• Computing tropical linear spaces
• Decomposing the secondary Cayley polytope
• Enumerating regular mixed-cell configurations
• ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS
• Four results on randomized incremental constructions
• How good are convex hull algorithms?
• On the complexity of computing determinants
• On the Newton polytope of the resultant
• The volume of the Newton polytope of a discriminant

Cited in

(5)

• Implicit representations of high-codimension varieties
• Numerical software to compute Newton polytopes and tropical membership
• Faster geometric algorithms via dynamic determinant computation
• An output-sensitive algorithm for computing projections of resultant polytopes
• Efficient edge-skeleton computation for polytopes defined by oracles

Describes a project that uses

Uses Software

• triangulation
• CGAL
• TropLi

This page was built for publication: An oracle-based, output-sensitive algorithm for projections of resultant polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875648)