kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The best ways to slice a polytope
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).ORCID iD: 0000-0002-5721-2325
Department of Mathematics, University of California, One Shields Avenue, Davis, California, 95616, United States, One Shields Avenue.
ETH Institute for Theoretical Studies, Clausiusstrasse 47, 8092 Zurich, Switzerland.
2025 (English)In: Mathematics of Computation, ISSN 0025-5718, E-ISSN 1088-6842, Vol. 94, no 352, p. 1003-1042Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
American Mathematical Society (AMS) , 2025. Vol. 94, no 352, p. 1003-1042
Keywords [en]
combinatorial types of polytopes, extremal problems on polytopes, hyperplane arrangements, hyperplane sections, integration over polyhedral regions, optimal slices, Polytopes, volume
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-358232DOI: 10.1090/mcom/4006ISI: 001286581600001Scopus ID: 2-s2.0-85213030527OAI: oai:DiVA.org:kth-358232DiVA, id: diva2:1924866
Note

QC 20250114

Available from: 2025-01-07 Created: 2025-01-07 Last updated: 2025-01-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Brandenburg, Marie-Charlotte

Search in DiVA

By author/editor
Brandenburg, Marie-Charlotte
By organisation
Mathematics (Div.)
In the same journal
Mathematics of Computation
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 41 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf