Polyhedral combinatorics of bisectors
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910772609679360 |
|---|---|
| author | Jal, Aryaman Jochemko, Katharina |
| author_facet | Jal, Aryaman Jochemko, Katharina |
| contents | For any polyhedral norm, the bisector of two points is a polyhedral complex. We study combinatorial aspects of this complex. We investigate the sensitivity of the presence of labelled maximal cells in the bisector relative to the position of the two points. We thereby extend work of Criado, Joswig and Santos (2022) who showed that for the tropical distance function the presence of maximal cells is encoded by a polyhedral fan, the bisection fan. We initiate the study of bisection cones and bisection fans with respect to arbitrary polyhedral norms. In particular, we show that the bisection fan always exists for polyhedral norms in two dimensions. Furthermore, we determine the bisection fan of the $\ell_{1}$-norm and the $\ell_{\infty}$-norm as well as the discrete Wasserstein distance in arbitrary dimensions. Intricate combinatorial structures, such as the resonance arrangement, make their appearance. We apply our results to obtain bounds on the combinatorial complexity of the bisectors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14372 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Polyhedral combinatorics of bisectors Jal, Aryaman Jochemko, Katharina Combinatorics Metric Geometry 46B20, 52B12, 52A21, 52C45 For any polyhedral norm, the bisector of two points is a polyhedral complex. We study combinatorial aspects of this complex. We investigate the sensitivity of the presence of labelled maximal cells in the bisector relative to the position of the two points. We thereby extend work of Criado, Joswig and Santos (2022) who showed that for the tropical distance function the presence of maximal cells is encoded by a polyhedral fan, the bisection fan. We initiate the study of bisection cones and bisection fans with respect to arbitrary polyhedral norms. In particular, we show that the bisection fan always exists for polyhedral norms in two dimensions. Furthermore, we determine the bisection fan of the $\ell_{1}$-norm and the $\ell_{\infty}$-norm as well as the discrete Wasserstein distance in arbitrary dimensions. Intricate combinatorial structures, such as the resonance arrangement, make their appearance. We apply our results to obtain bounds on the combinatorial complexity of the bisectors. |
| title | Polyhedral combinatorics of bisectors |
| topic | Combinatorics Metric Geometry 46B20, 52B12, 52A21, 52C45 |
| url | https://arxiv.org/abs/2308.14372 |