Le nombre de triangulations d'un ensemble de

Après avoir entendu Emo Welzl parler du sujet cet été, je sais que le nombre de triangulations d'un ensemble de points dans le plan se situe entre environ et . Toutes mes excuses si je ne suis pas à jour; les mises à jour sont les bienvenues. $n$ $\Omega(8.48^n)$ $O(30^n)$

J'ai mentionné cela en classe et je voulais enchaîner avec de brèves remarques sages pour donner aux étudiants une idée de (a) pourquoi il s'est avéré si difficile de fixer cette quantité, et (b) pourquoi tant de gens se soucient de la fixer. J'ai trouvé que je n'avais pas de réponses adéquates pour éclairer l'un ou l'autre problème; tant pis pour ma sagacité!

J'apprécierais votre point de vue sur ces questions certes vagues. Merci!

co.combinatorics cg.comp-geom Joseph O'Rourke
la source

Selon la page de polygonisation d'Erik Demaine , la limite indiquée dans la conférence était , mais je ne me souviens pas si Emo Welzl a déclaré que l'on pouvait montrer une meilleure limite en utilisant une analyse plus approfondie. Pour une raison quelconque, j'ai dans ma tête.

O (56^{n})

$O(56^n)$

O (35^{n})

$O(35^n)$

Timothy Sun

Sur la même page, il indique "La meilleure limite actuelle est 30". Le nombre 56 est pour la polygonisation.

Chao Xu

Il vaut peut-être la peine de donner mes propres réponses à mes questions. Les triangulations sont formées de segments non croisés. Comprendre la non-croisement est difficile. C'est un). Pour (b), la poursuite est conduite en essayant de comprendre le non-croisement. Je pense que vous conviendrez que ces réponses sont inadéquates.

Joseph O'Rourke

Comme point de référence, faire la même chose pour les points en position convexe est un exercice de devoirs via des nombres catalans. C'est parce que nous pouvons caractériser la non-traversée d'une manière agréable via des parenthèses équilibrées (donnant foi au point (a))

Suresh Venkat

Je pencherais pour dire que ce problème n'est pas directement lié à la SEE. Principalement parce qu'un problème clé caractérise les paires non croisées, et aussi parce qu'il y a une saveur topologique plutôt que géométrique beaucoup plus forte à cette question (et nous avons des preuves circonstancielles que l'EDC est intrinsèquement géométrique)

Suresh Venkat

Voici une raison de plus "appliquée" pour laquelle nous nous soucions des triangulations. Il existe un corpus de travaux sur la compression du maillage où le but est d'utiliser le moins de bits par sommet possible pour coder un maillage (principalement pour faciliter le stockage et la transmission). La base particulière de l'exposant dans le nombre de triangulations d'un ensemble de points planaires fournit une borne inférieure théorique sur le nombre de bits nécessaires par sommet (spécifiquement, triangulations signifie que vous avez besoin d'au moins 8,48 bits par sommet). Ces limites peuvent ensuite être comparées aux schémas de compression de maillage réels pour déterminer leur efficacité. $8.48^n$

Suresh Venkat
la source

Excellent point, Suresh! Je n'ai pas pensé à cette connexion.

Joseph O'Rourke

Le nombre de triangulations d'un ensemble de

Réponses: