research-article

An output-sensitive algorithm for computing projections of resultant polytopes

Authors:

Ioannis Z. Emiris,

Vissarion Fisikopoulos,

Christos Konaxis,

Luis PeñarandaAuthors Info & Claims

SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

Pages 179 - 188

https://doi.org/10.1145/2261250.2261276

Published: 17 June 2012 Publication History

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 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 35K, 23K or 500 vertices, resp., within 2hr. Compared to tropical geometry software, ours is faster up to dimension 5 or 6, and competitive in higher dimensions.

References

[1]

D. Avis. lrs: A revised implementation of the reverse search vertex enumeration algorithm. In Polytopes: Combinatorics & Computation, volume 29 of Oberwolfach Seminars, pages 177--198. 2000.

[2]

D. Avis, D. Bremner, and R. Seidel. How good are convex hull algorithms? Comput. Geom.: Theory & Appl., 7:265--301, 1997.

Digital Library

[3]

S. Basu, R. Pollack, and M.-F. Roy. Algorithms in real algebraic geometry. Springer-Verlag, Berlin, 2003.

Digital Library

[4]

J.-D. Boissonnat, O. Devillers, and S. Hornus. Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension. In Proc. SoCG, pages 208--216, 2009.

Digital Library

[5]

D. Bremner. Incremental convex hull algorithms are not output sensitive. In Proc. 7th Intern. Symp. Algorithms and Comput., pages 26--35, London, UK, 1996. Springer.

Digital Library

[6]

H. Brönnimann, I.Z. Emiris, V. Pan, and S. Pion. Sign determination in Residue Number Systems. Theor. Comp. Science, Spec. Issue on Real Numbers & Computers, 210(1):173--197, 1999.

Digital Library

[7]

CGAL: Computational geometry algorithms library. http://www.cgal.org.

[8]

K.L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. Comput. Geom.: Theory & Appl., 3:185--121, 1993.

Digital Library

[9]

D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Number 185 in GTM. Springer, New York, 2nd edition, 2005.

[10]

O. Devillers, 2011. Personal communication.

[11]

J.-G. Dumas, T. Gautier, M. Giesbrecht, P. Giorgi, B. Hovinen, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. Linbox: A generic library for exact linear algebra. In Proc. Intern. Congress Math. Software, pages 40--50, Beijing, 2002.

[12]

I.Z. Emiris, V. Fisikopoulos, and C. Konaxis. Regular triangulations and resultant polytopes. In Proc. Europ. Works. Comput. Geometry, Dortmund, 2010.

[13]

I.Z. Emiris, V. Fisikopoulos, and L. Penaranda. Optimizing the computation of sequences of determinantal predicates. In Proc. Europ. Workshop Computat. Geometry, Assisi, Italy, 2012.

[14]

I.Z. Emiris, T. Kalinka, and C. Konaxis. Implicitization using predicted support. In Proc. Intern. Works. Symbolic-Numeric Computation, 2011.

Digital Library

[15]

G. Fowler, L.C. Noll, and P. Vo. Fowler-Noll-Vo hash. www.isthe.com/chongo/tech/comp/fnv, 1991.

[16]

K. Fukuda. cdd and cdd+ Home Page. ETH Zaurich. www.ifor.math.ethz.ch/~fukuda/cdd_home/, 2008.

[17]

E. Gawrilow and M. Joswig. Polymake: an approach to modular software design in computational geometry. In Proc. Annual ACM Symp. Computational Geometry, pages 222--231. ACM Press, 2001.

Digital Library

[18]

I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhauser, Boston, 1994.

[19]

G. Guennebaud, B. Jacob, et al. Eigen v3. http://eigen.tuxfamily.org, 2010.

[20]

D. James. Boost functional library. www.boost.org/libs/functional/hash, 2008.

[21]

A. Jensen and J. Yu. Computing tropical resultants. arXiv:math.AG/1109.2368v1, 2011.

[22]

M. Joswig. Beneath-and-beyond revisited. In M. Joswig and N. Takayama, editors, Algebra, Geometry, and Software Systems, Mathematics and Visualization. Springer, Berlin, 2003.

[23]

E. Kaltofen and G. Villard. On the complexity of computing determinants. Computational Complexity, 13:91--130, 2005.

Digital Library

[24]

M.M. Kapranov. Characterization of A-discriminantal hypersurfaces in terms of logarithmic Gauss map. Math. Annalen, 290:277--285, 1991.

[25]

J.A. De Loera, J. Rambau, and F. Santos. Triangulations: Structures for Algorithms and Applications, volume 25 of Algorithms and Computation in Mathematics. Springer, 2010.

Digital Library

[26]

T. Michiels and R. Cools. Decomposing the secondary Cayley polytope. Discr. Comput. Geometry, 23:367--380, 2000.

[27]

T. Michiels and J. Verschelde. Enumerating regular mixed-cell configurations. Discr. Comput. Geometry, 21(4):569--579, 1999.

[28]

J. Rambau. TOPCOM: Triangulations of point configurations and oriented matroids. In Proc. Intern. Congress Math. Software, pages 330--340, 2002.

[29]

B. Sturmfels. On the Newton polytope of the resultant. J. Algebraic Combin., 3:207--236, 1994.

Digital Library

[30]

B. Sturmfels and J. Yu. Tropical implicitization and mixed fiber polytopes. In Software for Algebraic Geometry, volume 148 of IMA Volumes in Math. & its Applic., pages 111--131. Springer, New York, 2008.

[31]

G.M. Ziegler. Lectures on Polytopes. Springer, 1995.

Cited By

Emiris IKarasoulou A(2014)Sparse Discriminants and ApplicationsFuture Vision and Trends on Shapes, Geometry and Algebra10.1007/978-1-4471-6461-6_4(55-71)Online publication date: 14-Jun-2014
https://doi.org/10.1007/978-1-4471-6461-6_4
Dickenstein AEmiris IFisikopoulos VMonagan MCooperman GGiesbrecht M(2013)Combinatorics of 4-dimensional resultant polytopesProceedings of the 38th International Symposium on Symbolic and Algebraic Computation10.1145/2465506.2465937(173-180)Online publication date: 26-Jun-2013
https://dl.acm.org/doi/10.1145/2465506.2465937
Emiris IKalinka T(2013)Sparse implicitization using support predictionACM Communications in Computer Algebra10.1145/2429135.242914746:3/4(88-89)Online publication date: 15-Jan-2013
https://dl.acm.org/doi/10.1145/2429135.2429147
Show More Cited By

Index Terms

An output-sensitive algorithm for computing projections of resultant polytopes
1. Mathematics of computing
  1. Mathematical software
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Combinatorics of 4-dimensional resultant polytopes
ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

The Newton polytope of the resultant, or resultant polytope, characterizes the resultant polynomial more precisely than total degree. The combinatorics of resultant polytopes are known in the Sylvester case [Gelfand et al.90] and up to dimension 3 [...
Convex hulls of spheres and convex hulls of disjoint convex polytopes

Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Given a set Σ of spheres in E^d, with d≥3 and d odd, having a fixed number of m distinct radii ρ₁,ρ₂,...,ρ_m, we show that the worst-case combinatorial complexity of the convex hull CH_d(Σ) of Σ is Θ(Σ_{{1≤i≠j≤m}}n_in_j^{⌊ d/2 ⌋}), where n_i is the number of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

June 2012

436 pages

ISBN:9781450312998

DOI:10.1145/2261250

Program Chairs:
Tamal Dey
The Ohio State University, USA
,
Sue Whitesides
University of Victoria, Canada

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '12

Sponsor:

SoCG '12: Symposium on Computational Geometry 2012

June 17 - 20, 2012

North Carolina, Chapel Hill, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
124
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Emiris IKarasoulou A(2014)Sparse Discriminants and ApplicationsFuture Vision and Trends on Shapes, Geometry and Algebra10.1007/978-1-4471-6461-6_4(55-71)Online publication date: 14-Jun-2014
https://doi.org/10.1007/978-1-4471-6461-6_4
Dickenstein AEmiris IFisikopoulos VMonagan MCooperman GGiesbrecht M(2013)Combinatorics of 4-dimensional resultant polytopesProceedings of the 38th International Symposium on Symbolic and Algebraic Computation10.1145/2465506.2465937(173-180)Online publication date: 26-Jun-2013
https://dl.acm.org/doi/10.1145/2465506.2465937
Emiris IKalinka T(2013)Sparse implicitization using support predictionACM Communications in Computer Algebra10.1145/2429135.242914746:3/4(88-89)Online publication date: 15-Jan-2013
https://dl.acm.org/doi/10.1145/2429135.2429147
Fisikopoulos VPeñaranda L(2012)Faster geometric algorithms via dynamic determinant computationProceedings of the 20th Annual European conference on Algorithms10.1007/978-3-642-33090-2_39(443-454)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33090-2_39

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten