The best ways to slice a Polytope

Brandenburg, Marie-Charlotte; De Loera, Jesús; Meroni, Chiara

doi:10.1090/mcom/4006

The best ways to slice a Polytope
HTML articles powered by AMS MathViewer

by Marie-Charlotte Brandenburg, Jesús A. De Loera and Chiara Meroni;

Math. Comp. 94 (2025), 1003-1042

DOI: https://doi.org/10.1090/mcom/4006

Published electronically: August 7, 2024

HTML | PDF | Request permission

Abstract:

We study the structure of the set of all possible affine hyperplane sections of a convex polytope. We present two different cell decompositions of this set, induced by hyperplane arrangements. Using our decomposition, we bound the number of possible combinatorial types of sections and craft algorithms that compute optimal sections of the polytope according to various combinatorial and metric criteria, including sections that maximize the number of $k$-dimensional faces, maximize the volume, and maximize the integral of a polynomial. Our optimization algorithms run in polynomial time in fixed dimension, but the same problems show computational complexity hardness otherwise. Our tools can be extended to intersection with halfspaces and projections onto hyperplanes. Finally, we present several experiments illustrating our theorems and algorithms on famous polytopes.

References

N. Amenta and G. M. Ziegler, Shadows and Slices of Polytopes, Proceedings of the Twelfth Annual Symposium on Computational Geometry (New York, NY, USA), SCG ’96, Association for Computing Machinery, 1996, pp. 10–19.
Federico Ardila, Anna Schindler, and Andrés R. Vindas-Meléndez, The equivariant volumes of the permutahedron, Discrete Comput. Geom. 65 (2021), no. 3, 618–635. MR 4226485, DOI 10.1007/s00454-019-00146-2
Velleda Baldoni, Nicole Berline, Jesus A. De Loera, Matthias Köppe, and Michele Vergne, How to integrate a polynomial over a simplex, Math. Comp. 80 (2011), no. 273, 297–325. MR 2728981, DOI 10.1090/S0025-5718-2010-02378-6
Keith Ball, Cube slicing in $\textbf {R}^n$, Proc. Amer. Math. Soc. 97 (1986), no. 3, 465–473. MR 840631, DOI 10.1090/S0002-9939-1986-0840631-0
Keith Ball, Volumes of sections of cubes and related problems, Geometric aspects of functional analysis (1987–88), Lecture Notes in Math., vol. 1376, Springer, Berlin, 1989, pp. 251–260. MR 1008726, DOI 10.1007/BFb0090058
Imre Bárány and Péter Frankl, How (not) to cut your cheese, Amer. Math. Monthly 128 (2021), no. 6, 543–552. MR 4265480, DOI 10.1080/00029890.2021.1901463
Alexander Barvinok, A course in convexity, Graduate Studies in Mathematics, vol. 54, American Mathematical Society, Providence, RI, 2002. MR 1940576, DOI 10.1090/gsm/054
Alexander Barvinok and James E. Pommersheim, An algorithmic theory of lattice points in polyhedra, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 91–147. MR 1731815
Saugata Basu, Richard Pollack, and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd ed., Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006. MR 2248869
Katalin Berlow, Marie-Charlotte Brandenburg, Chiara Meroni, and Isabelle Shankar, Intersection bodies of polytopes, Beitr. Algebra Geom. 63 (2022), no. 2, 419–439. MR 4429334, DOI 10.1007/s13366-022-00621-7
L. J. Billera, M. M. Kapranov, and B. Sturmfels, Cellular strings on polytopes, Proc. Amer. Math. Soc. 122 (1994), no. 2, 549–555. MR 1205482, DOI 10.1090/S0002-9939-1994-1205482-0
Louis J. Billera and Bernd Sturmfels, Fiber polytopes, Ann. of Math. (2) 135 (1992), no. 3, 527–549. MR 1166643, DOI 10.2307/2946575
M.-C. Brandenburg, J. A. De Loera, and C. Meroni, MATHREPO. Mathematical data and software, 2023, https://mathrepo.mis.mpg.de/BestSlicePolytopes/
M.-C. Brandenburg and C. Meroni, Intersection bodies of polytopes: Translations and convexity, J. Algebr. Comb., 60 (2024), 127–143, DOI:10.1007/s10801-024-01328-9
Graham Brightwell and Peter Winkler, Counting linear extensions, Order 8 (1991), no. 3, 225–242. MR 1154926, DOI 10.1007/BF00383444
G. D. Chakerian and P. Filliman, The measures of the projections of a cube, Studia Sci. Math. Hungar. 21 (1986), no. 1-2, 103–110. MR 898848
Don Chakerian and Dave Logothetti, Cube slices, pictorial triangles, and probability, Math. Mag. 64 (1991), no. 4, 219–241. MR 1131009, DOI 10.2307/2690829
Jesús A. De Loera, Jörg Rambau, and Francisco Santos, Triangulations, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010. Structures for algorithms and applications. MR 2743368, DOI 10.1007/978-3-642-12971-1
M. E. Dyer and A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM J. Comput. 17 (1988), no. 5, 967–974. MR 961051, DOI 10.1137/0217060
Martin Dyer, Peter Gritzmann, and Alexander Hufnagel, On the complexity of computing mixed volumes, SIAM J. Comput. 27 (1998), no. 2, 356–400. MR 1616544, DOI 10.1137/S0097539794278384
P. Filliman, The volume of duals and sections of polytopes, Mathematika 39 (1992), no. 1, 67–80. MR 1176472, DOI 10.1112/S0025579300006860
Ansgar Freyer and Martin Henk, Bounds on the lattice point enumerator via slices and projections, Discrete Comput. Geom. 67 (2022), no. 3, 895–918. MR 4393084, DOI 10.1007/s00454-021-00310-7
Hiroshi Fukuda, Nobuaki Muto, Kikuko Goto, and Gisaku Nakamura, Sections of hyper-cube in five dimensions, Forma 12 (1997), no. 1, 15–33. MR 1473339
Komei Fukuda, Shigemasa Saito, Akihisa Tamura, and Takeshi Tokuyama, Bounding the number of $k$-faces in arrangements of hyperplanes, Discrete Appl. Math. 31 (1991), no. 2, 151–165. First Canadian Conference on Computational Geometry (Montreal, PQ, 1989). MR 1106697, DOI 10.1016/0166-218X(91)90067-7
Richard J. Gardner, Geometric tomography, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 58, Cambridge University Press, New York, 2006. MR 2251886, DOI 10.1017/CBO9781107341029
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979. A guide to the theory of NP-completeness. MR 519066
Apostolos Giannopoulos, Alexander Koldobsky, and Artem Zvavitch, Inequalities for sections and projections of convex bodies, Harmonic analysis and convexity, Adv. Anal. Geom., vol. 9, De Gruyter, Berlin, [2023] ©2023, pp. 223–256. MR 4654480
Nick Gravin, Jean Lasserre, Dmitrii V. Pasechnik, and Sinai Robins, The inverse moment problem for convex polytopes, Discrete Comput. Geom. 48 (2012), no. 3, 596–621. MR 2957634, DOI 10.1007/s00454-012-9426-4
Peter Gritzmann and Victor Klee, On the complexity of some basic problems in computational convexity. I. Containment problems, Discrete Math. 136 (1994), no. 1-3, 129–174. Trends in discrete mathematics. MR 1313285, DOI 10.1016/0012-365X(94)00111-U
Peter Gritzmann and Victor Klee, On the complexity of some basic problems in computational convexity. II. Volume and mixed volumes, Polytopes: abstract, convex and computational (Scarborough, ON, 1993) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 440, Kluwer Acad. Publ., Dordrecht, 1994, pp. 373–466. MR 1322071
Peter Gritzmann and Victor Klee, Computational convexity, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 491–515. MR 1730183
Branko Grünbaum, Convex polytopes, Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. MR 226496
D. S. Johnson and F. P. Preparata, The densest hemisphere problem, Theoret. Comput. Sci. 6 (1978), no. 1, 93–107. MR 464674, DOI 10.1016/0304-3975(78)90006-3
Leonid Khachiyan, Complexity of polytope volume computation, New trends in discrete and computational geometry, Algorithms Combin., vol. 10, Springer, Berlin, 1993, pp. 91–101. MR 1228040, DOI 10.1007/978-3-642-58043-7_{5}
Askold Khovanskii, Combinatorics of sections of polytopes and Coxeter groups in Lobachevsky spaces, The Coxeter legacy, Amer. Math. Soc., Providence, RI, 2006, pp. 129–157. MR 2209026
Bo’az Klartag, Logarithmic bounds for isoperimetry and slices of convex sets, Ars Inven. Anal. (2023), Paper No. 4, 17. MR 4603941
Bo’az Klartag and Joseph Lehec, Bourgain’s slicing problem and KLS isoperimetry up to polylog, Geom. Funct. Anal. 32 (2022), no. 5, 1134–1159. MR 4498841, DOI 10.1007/s00039-022-00612-9
B. Klartag and V. Milman, The Slicing Problem by Bourgain, Analysis at Large: Dedicated to the Life and Work of Jean Bourgain (Artur Avila, Michael Th. Rassias, and Yakov Sinai, eds.), Springer International Publishing, Cham, 2022, pp. 203–231.
Alexander Koldobsky, Fourier analysis in convex geometry, Mathematical Surveys and Monographs, vol. 116, American Mathematical Society, Providence, RI, 2005. MR 2132704, DOI 10.1090/surv/116
Hermann König, Non-central sections of the simplex, the cross-polytope and the cube, Adv. Math. 376 (2021), Paper No. 107458, 35. MR 4178930, DOI 10.1016/j.aim.2020.107458
Astrid Kousholt and Julia Schulte, Reconstruction of convex bodies from moments, Discrete Comput. Geom. 65 (2021), no. 1, 1–42. MR 4194435, DOI 10.1007/s00454-020-00225-9
Jean B. Lasserre, Simple formula for integration of polynomials on a simplex, BIT 61 (2021), no. 2, 523–533. MR 4258026, DOI 10.1007/s10543-020-00828-x
Jean B. Lasserre and Konstantin E. Avrachenkov, The multi-dimensional version of $\int ^b_a x^p dx$, Amer. Math. Monthly 108 (2001), no. 2, 151–154. MR 1818188, DOI 10.2307/2695528
Jim Lawrence, Cutting the $d$-cube, J. Res. Nat. Bur. Standards 84 (1979), no. 1, 51–53 (1978). MR 527768, DOI 10.6028/jres.084.004
Jim Lawrence, Polytope volume computation, Math. Comp. 57 (1991), no. 195, 259–271. MR 1079024, DOI 10.1090/S0025-5718-1991-1079024-2
Ruoyuan Liu and Tomasz Tkocz, A note on the extremal non-central sections of the cross-polytope, Adv. in Appl. Math. 118 (2020), 102031, 17. MR 4081431, DOI 10.1016/j.aam.2020.102031
Erwin Lutwak, Intersection bodies and dual mixed volumes, Adv. in Math. 71 (1988), no. 2, 232–261. MR 963487, DOI 10.1016/0001-8708(88)90077-1
Mathieu Meyer and Alain Pajor, Sections of the unit ball of $L^n_p$, J. Funct. Anal. 80 (1988), no. 1, 109–123. MR 960226, DOI 10.1016/0022-1236(88)90068-7
James Moody, Corey Stone, David Zach, and Artem Zvavitch, A remark on the extremal non-central sections of the unit cube, Asymptotic geometric analysis, Fields Inst. Commun., vol. 68, Springer, New York, 2013, pp. 211–228. MR 3076152, DOI 10.1007/978-1-4614-6406-8_{9}
Piotr Nayar and Tomasz Tkocz, Extremal sections and projections of certain convex bodies: a survey, Harmonic analysis and convexity, Adv. Anal. Geom., vol. 9, De Gruyter, Berlin, [2023] ©2023, pp. 343–390. MR 4654482
Arnau Padrol and Julian Pfeifle, Polygons as sections of higher-dimensional polytopes, Electron. J. Combin. 22 (2015), no. 1, Paper 1.24, 16. MR 3315466, DOI 10.37236/4315
Arnau Padrol and Eva Philippe, Sweeps, polytopes, oriented matroids, and allowable graphs of permutations, Combinatorica 44 (2024), no. 1, 63–123. MR 4707565, DOI 10.1007/s00493-023-00062-3
Lionel Pournin, Shallow sections of the hypercube, Israel J. Math. 255 (2023), no. 2, 685–704. MR 4619551, DOI 10.1007/s11856-022-2400-9
The Sage Developers, Sagemath, the Sage Mathematics Software System (Version 9.2), 2021, https://www.sagemath.org
Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Second expanded edition, Encyclopedia of Mathematics and its Applications, vol. 151, Cambridge University Press, Cambridge, 2014. MR 3155183
Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
Richard P. Stanley, An introduction to hyperplane arrangements, Geometric combinatorics, IAS/Park City Math. Ser., vol. 13, Amer. Math. Soc., Providence, RI, 2007, pp. 389–496. MR 2383131, DOI 10.1090/pcms/013/08
Jeffrey D. Vaaler, A geometric inequality with applications to linear forms, Pacific J. Math. 83 (1979), no. 2, 543–553. MR 557952
D. W. Walkup, A simplex with a large cross section, Amer. Math. Monthly 75 (1968), 34–36. MR 226506, DOI 10.2307/2315102
Simon Webb, Central slices of the regular simplex, Geom. Dedicata 61 (1996), no. 1, 19–28. MR 1389634, DOI 10.1007/BF00149416
Wolfram Research, Inc., Mathematica (Version 13.2), 2022, Champaign, IL.
Thomas Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc. 1 (1975), no. issue 1, 154, vii+102. MR 357135, DOI 10.1090/memo/0154
Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1