El número de triangulaciones de un conjunto de

Después de escuchar a Emo Welzl hablar sobre el tema este verano, sé que el número de triangulaciones de un conjunto de puntos en el plano está entre y . Disculpas si estoy desactualizado; actualizaciones bienvenidas. $n$ $\Omega(8.48^n)$ $O(30^n)$

Mencioné esto en clase y quería hacer un seguimiento con breves y sabios comentarios para darles a los estudiantes una idea de (a) por qué ha resultado tan difícil determinar esta cantidad, y (b) por qué tantos se preocupan por precisarlo. Descubrí que no tenía respuestas adecuadas para iluminar ninguno de los dos temas; ¡tanto por mi sabiduría!

Le agradecería su opinión sobre estas preguntas ciertamente vagas. ¡Gracias!

co.combinatorics cg.comp-geom Joseph O'Rourke
fuente

O (56^{n})

$O(56^n)$

O (35^{n})

$O(35^n)$

En la misma página, dice "El mejor límite actual es 30". El número 56 es para poligonalización.

Chao Xu

Quizás valga la pena dar mis propias respuestas a mis preguntas. Las triangulaciones están formadas por segmentos no cruzados. Comprender la falta de cruce es difícil. Eso es un). Para (b), la búsqueda se lleva a cabo tratando de comprender el no cruce. Creo que estará de acuerdo en que estas respuestas son inadecuadas.

Joseph O'Rourke

Como punto de referencia, hacer lo mismo para los puntos en posición convexa es un ejercicio de tarea a través de números catalanes. Esto se debe a que podemos caracterizar la no cruza de una manera agradable a través de paréntesis equilibrados (dando crédito al punto (a))

Suresh Venkat

Me inclinaría por decir que este problema no está directamente relacionado con el EDC. Principalmente porque una cuestión clave es caracterizar pares no cruzados, y también porque hay un sabor topológico mucho más fuerte que geométrico en esta pregunta (y tenemos evidencia circunstancial de que el EDC es intrínsecamente geométrico)

Suresh Venkat

El número de triangulaciones de un conjunto de

Respuestas: