×

Parallel enumeration of triangulations. (English) Zbl 1393.68175

Summary: We report on the implementation of an algorithm for computing the set of all regular triangulations of finitely many points in Euclidean space. This algorithm, which we call down-flip reverse search, can be restricted, e.g., to computing full triangulations only; this case is particularly relevant for tropical geometry. Most importantly, down-flip reverse search allows for massive parallelization, i.e., it scales well even for many cores. Our implementation allows to compute the triangulations of much larger point sets than before.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] David Avis and Luc Devroye, An analysis of budgeted parallel search on conditional Galton-Watson trees, 2017, PreprintarXiv:1703.10731. the electronic journal of combinatorics 25(3) (2018), #P3.625
[2] David Avis and Komei Fukuda, Reverse search for enumeration., Discrete Appl. Math. 65 (1996), no. 1-3, 21-46 (English). · Zbl 0854.68070
[3] David Avis and Charles Jordan, A parallel framework for reverse search using mts, 2016, PreprintarXiv:1610.07735.
[4] , mplrs: A scalable parallel vertex/facet enumeration code, Mathematical Programming Computation 10 (2018), no. 2, 267-302. · Zbl 1400.90222
[5] David Bremner, Mathieu Dutour Sikiri´c, and Achill Sch¨urmann, Polyhedral representation conversion up to symmetries, Polyhedral computation, CRM Proc. Lecture Notes, vol. 48, Amer. Math. Soc., Providence, RI, 2009, pp. 45-71. MR 2503772 · Zbl 1170.68621
[6] Adrian Br¨ungger, Ambros Marzetta, Komei Fukuda, and Jurg Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), 45-63. · Zbl 0937.90088
[7] Jes´us A. De Loera, J¨org Rambau, and Francisco Santos, Triangulations, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010, Structures for algorithms and applications. MR 2743368 (2011j:52037)
[8] Paul H. Edelman and Victor Reiner, The higher Stasheff-Tamari posets., Mathematika 43 (1996), no. 1, 127-154 (English). · Zbl 0854.06003
[9] J.-A. Ferrez, K. Fukuda, and Th. M. Liebling, Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, European J. Oper. Res. 166 (2005), no. 1, 35-50. MR 2128976 · Zbl 1066.90101
[10] Komei Fukuda, cddlib, version 0.94h,http://www.inf.ethz.ch/personal/ fukudak/cdd_home/, 2015.
[11] Ewgenij Gawrilow and Michael Joswig, polymake: a framework for analyzing convex polytopes, Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol. 29, Birkh¨auser, Basel, 2000, pp. 43-73. MR MR1785292 (2001f:52033) · Zbl 0960.68182
[12] I. M. Gel0fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants and multidimensional determinants, Modern Birkh¨auser Classics, Birkh¨auser Boston Inc., Boston, MA, 2008, Reprint of the 1994 edition. MR MR2394437 (2009a:14065)
[13] Hiroshi Imai, Tomonari Masada, Fumihiko Takeuchi, and Keiko Imai, Enumerating triangulations in general dimensions, Internat. J. Comput. Geom. Appl. 12 (2002), no. 6, 455-480. MR 1945594 · Zbl 1045.05006
[14] Anders N. Jensen, An implementation of exact mixed volume computation, Mathematical Software - ICMS 2016: 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings (Gert-Martin Greuel, Thorsten Koch, Peter Paule, and Andrew Sommese, eds.), Springer International Publishing, Cham, 2016, pp. 198-205. · Zbl 1437.14009
[15] , Tropical homotopy continuation, 2016, PreprintarXiv:1601.02818.
[16] , Gfan, a software system for Gr¨obner fans and tropical varieties, version 0.6, Available athttp://home.imf.au.dk/jensen/software/gfan/gfan.html, 2017.
[17] Mikhail M. Kapranov and Vladimir A. Voevodsky, Combinatorial-geometric aspects of polycategory theory: pasting schemes and higher Bruhat orders (list of results), the electronic journal of combinatorics 25(3) (2018), #P3.626 Cahiers Topologie G´eom. Diff´erentielle Cat´eg. 32 (1991), no. 1, 11-27, International Category Theory Meeting (Bangor, 1989 and Cambridge, 1990). MR 1130400
[18] Diane Maclagan and Bernd Sturmfels, Introduction to tropical geometry, Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015. MR 3287221 · Zbl 1321.14048
[19] Nicholas Nethercote and Julian Seward, Valgrind: A framework for heavyweight dynamic binary instrumentation, Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (New York, NY, USA), PLDI ’07, ACM, 2007, pp. 89-100.
[20] David Orden and Francisco Santos, Asymptotically efficient triangulations of the d-cube, Discrete Comput. Geom. 30 (2003), no. 4, 509-528. MR 2013970 · Zbl 1042.52009
[21] Julian Pfeifle, Secondary polytope of the “mother of all examples”, Electronic Geometry Models (2000), No. 2000.09.033. · Zbl 1053.52017
[22] Julian Pfeifle and J¨org Rambau, Computing triangulations using oriented matroids, Algebra, geometry, and software systems, Springer, Berlin, 2003, pp. 49-75. MR 2011753 (2004i:68233) · Zbl 1027.52015
[23] Lionel Pournin, The flip-graph of the 4-dimensional cube is connected, Discrete Comput. Geom. 49 (2013), no. 3, 511-530. MR 3038527 · Zbl 1267.05156
[24] Lionel Pournin and Thomas M. Liebling, Constrained paths in the flip-graph of regular triangulations, Comput. Geom. 37 (2007), no. 2, 134-140. MR 2310598 · Zbl 1123.68132
[25] J¨org Rambau, TOPCOM: triangulations of point configurations and oriented matroids, Mathematical software (Beijing, 2002), World Sci. Publ., River Edge, NJ, 2002, pp. 330-340. MR 1932619 · Zbl 1057.68150
[26] J¨org Rambau and Victor Reiner, A survey of the higher Stasheff-Tamari orders., Associahedra, Tamari lattices and related structures. Tamari memorial Festschrift, Basel: Birkh¨auser, 2012, pp. 351-390 (English). · Zbl 1280.52010
[27] Thomas Rehn and Achill Sch¨urmann, C++ tools for exploiting polyhedral symmetries., Mathematical software - ICMS 2010. Third international congress on mathematical software, Kobe, Japan, September 13-17, 2010. Proceedings, Berlin: Springer, 2010, pp. 295-298 (English). · Zbl 1295.52020
[28] Benjamin Schr¨oter, Multi-splits and tropical linear spaces from nested matroids, 2017, PreprintarXiv:1707.02814.
[29] ´Akos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241
[30] Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker, and Jack Dongarra, MPI- the complete reference, vol 1: The MPI core, 2nd ed., MIT Press, 1998.
[31] Christophe Weibel, Implementation and parallelization of a reverse-search algorithm for Minkowski sums, 2010 Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments (ALENEX), 2010, pp. 34-42. the electronic journal of combinatorics 25(3) (2018), #P3.627
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.