2026-08-17T04:51:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19968 2024-06-06T06:21:14Z ddc:004 open_access

A Canonical Tree Decomposition for Chirotopes Bouvel, Mathilde Feray, Valentin Goaoc, Xavier Koechlin, Florent Order type modular decomposition counting triangulations mutually avoiding point sets generating functions rewriting systems 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, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mathilde Bouvel and Valentin Feray and Xavier Goaoc and Florent Koechlin 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.23 urn:nbn:de:0030-drops-199680 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.23 eng https://creativecommons.org/licenses/by/4.0/legalcode