Multitriangulations as complexes of star polygons (Q1017914)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Multitriangulations as complexes of star polygons |
scientific article |
Statements
Multitriangulations as complexes of star polygons (English)
0 references
13 May 2009
0 references
A \textit{multitriangulation} of order \(k\), or \(k\)-triangulation, of a convex \(n\)-gon is a maximal set of edges such that no \(k+1\) of them mutually cross. A \textit{flip} between \(k\)-triangulations creates one \(k\)-triangulation from another one, removing and inserting a single edge. The \textit{length} of an edge \([p_i,p_j]\) between \(n\) points \(p_1,\dots ,p_n\) in convex position and labeled cyclically is defined as \(\min\{|j - i|,|i - j |\}\) mod \(n\). If \(p,q\) are two coprime integers, a \textit{star-polygon} of type \(\{p/q\}\) is a polygon formed by connecting a set \(V=\{s_j\:|\:j\in\mathbb{Z}_p\}\) of \(p\) points on the unit circle with the set \(E=\{[s_j,s_{j+q}]\:|\:j\in \mathbb{Z}_p\}\). The notion of \(k\)-triangulation has been widely explored from many points of view. In this paper the authors introduce a new one, namely as complexes of star polygons of type \(\{2k+1/k\}\), called \textit{\(k\)-stars}. Let \(T\) be a \(k\)-triangulation of the \(n\)-gon, \(n\geq 2k+1\). The main results of the paper are the following (at the end of the paper the authors point out that such results have been independently discovered by \textit{A. Dress, S. Grünewald, J. Jonsson}, and \textit{V. Moulton}, in ``The simplicial complex \(\varDelta _{n,k}\) of \(k\)-compatible line arrangements in the hyperbolic plane. Part 1: The structure of \(\varDelta _{n,k}\),'' preprint (2007). {\parindent5mm \begin{itemize}\item[1)] \(T\) contains exactly \(n- 2k\) \(k\)-stars; \item[2)] each edge of \(T\) belongs to zero, one or two \(k\)-stars, depending on whether its length is smaller, equal or greater than \(k\); \item[3)] Any common edge \(f\) of two \(k\)-stars \(R\) and \(S\) of \(T\) can be flipped to another edge \(e\) so that \(T\triangle\{e,f\}\) is a \(k\)-triangulation. Moreover, the edges \(e\) and \(f\) depend only on \(R\cup S\), not the rest of \(T\). \end{itemize}} It is the authors' opinion that \(k\)-stars are the right way of looking at \(k\)-triangulations. As evidence for this, they also give new proofs of basic properties of \(k\)-triangulations, which, in contrast with the proofs previously appeared in the literature, are just based on simple combinatorial properties of \(k\)-stars. The paper ends with a discussion on possible developments of the new approach to further problems.
0 references
generalized triangulation
0 references
crossing-free graph
0 references
star polygons
0 references
flips
0 references
associahedron
0 references