The Best Ways to Slice a Polytope
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910974205755392 |
|---|---|
| author | Brandenburg, Marie-Charlotte De Loera, Jesús A. Meroni, Chiara |
| author_facet | Brandenburg, Marie-Charlotte De Loera, Jesús A. Meroni, Chiara |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_14239 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Best Ways to Slice a Polytope Brandenburg, Marie-Charlotte De Loera, Jesús A. Meroni, Chiara Combinatorics Metric Geometry Optimization and Control 52B55, 52C35, 52A38, 52A40, 52B11, 90C27, 52C45, 14P10 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 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. |
| title | The Best Ways to Slice a Polytope |
| topic | Combinatorics Metric Geometry Optimization and Control 52B55, 52C35, 52A38, 52A40, 52B11, 90C27, 52C45, 14P10 |
| url | https://arxiv.org/abs/2304.14239 |