DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.23

A Canonical Tree Decomposition for Chirotopes

Authors: Mathilde Bouvel, Valentin Feray, Xavier Goaoc, and Florent Koechlin

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

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.

Cite as

Mathilde Bouvel, Valentin Feray, Xavier Goaoc, and Florent Koechlin. A Canonical Tree Decomposition for Chirotopes. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bouvel_et_al:LIPIcs.SoCG.2024.23,
  author =	{Bouvel, Mathilde and Feray, Valentin and Goaoc, Xavier and Koechlin, Florent},
  title =	{{A Canonical Tree Decomposition for Chirotopes}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.23},
  URN =		{urn:nbn:de:0030-drops-199680},
  doi =		{10.4230/LIPIcs.SoCG.2024.23},
  annote =	{Keywords: Order type, modular decomposition, counting triangulations, mutually avoiding point sets, generating functions, rewriting systems}
}

Search Results

Documents authored by Feray, Valentin

A Canonical Tree Decomposition for Chirotopes

Abstract

Cite as

Thanks for your feedback!

Could not send message