A canonical tree decomposition for order types, and some applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917689689112576 |
|---|---|
| author | Bouvel, Mathilde Féray, Valentin Goaoc, Xavier Koechlin, Florent |
| author_facet | Bouvel, Mathilde Féray, Valentin Goaoc, Xavier Koechlin, Florent |
| contents | We introduce and study a notion of decomposition of planar point sets (or rather of their chirotopes) as trees decorated by smaller chirotopes. This decomposition is based on the concept of mutually avoiding sets (which we rephrase as \emph{modules}), and adapts in some sense the modular decomposition of graphs in the world of chirotopes. The associated tree always exists and is unique up to some appropriate constraints. We also show how to compute the number of triangulations of a chirotope efficiently, starting from its tree and the (weighted) numbers of triangulations of its parts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_10311 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A canonical tree decomposition for order types, and some applications Bouvel, Mathilde Féray, Valentin Goaoc, Xavier Koechlin, Florent Computational Geometry Combinatorics We introduce and study a notion of decomposition of planar point sets (or rather of their chirotopes) as trees decorated by smaller chirotopes. This decomposition is based on the concept of mutually avoiding sets (which we rephrase as \emph{modules}), and adapts in some sense the modular decomposition of graphs in the world of chirotopes. The associated tree always exists and is unique up to some appropriate constraints. We also show how to compute the number of triangulations of a chirotope efficiently, starting from its tree and the (weighted) numbers of triangulations of its parts. |
| title | A canonical tree decomposition for order types, and some applications |
| topic | Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2403.10311 |