DMTCS Proceedings, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)

Font Size:  Small  Medium  Large

Multi-triangulations as complexes of star polygons

Vincent Pilaud, Francisco Santos

Abstract


A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross. k-triangulations have received attention in recent literature, with motivation coming from several interpretations of them. We present a new way of looking at k-triangulations, where certain star polygons naturally generalize triangles for k-triangulations. With this tool we give new, direct proofs of the fundamental properties of k-triangulations (number of edges, definition of flip). This interpretation also opens up new avenues of research that we briefly explore in the last section.
Résumé. Une k-triangulation d'un polygone convexe est un ensemble maximal de diagonales ne contenant pas k+1 arêtes qui se croisent deux à deux. Les k-triangulations ont été récemment étudiées sous divers aspects dans la littérature. On présente ici un nouveau point de vue sur les k-triangulations, en introduisant certains polygones étoilés comme généralisation des triangles pour les k-triangulations. En utilisant ce nouvel outil, on donne des preuves directes des propriétés fondamentales des k-triangulations (nombre d'arêtes, définition du flip). Notre point de vue ouvre par ailleurs de nouveaux horizons de recherche que l'on présente rapidement dans la dernière partie.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional