Dobles de triangulación únicos de polígonos simples

Dada una triangulación (sin puntos Steiner) de un polígono simple , uno puede considerar el doble de esta triangulación, que se define de la siguiente manera. Creamos un vértice para cada triángulo en nuestra triangulación, y conectamos dos vértices si los triángulos correspondientes comparten un borde. Se sabe que el gráfico dual es un árbol con un grado máximo de tres. $P$

Para mi aplicación, estoy interesado en lo siguiente. Dado un árbol con un grado máximo de tres, ¿hay siempre un polígono simple tal que el doble de cada triangulación (sin puntos Steiner) de sea igual a ? Aquí, la triangulación de puede no ser única, pero requiero que el gráfico dual sea único. $T$ $P$ $P$ $T$ $P$

Esto es cierto cuando es un camino, pero no queda claro cuando tienes vértices de grado tres. $T$

reference-request computational-geometry Nizbel99
fuente

El gráfico dual no es necesariamente un árbol. Considere esta forma de estrella , que según su definición de compartir un borde (total o parcial) es un gráfico disjunto de 4 vértices o un ciclo de 4.

orlp

¡Buena atrapada! Olvidé mencionar que no permito puntos Steiner en mis triangulaciones. Actualizaré la pregunta.

Nizbel99

Pregunta interesante, pero tengo curiosidad sobre qué aplicación puede tener esto. ¿Puedes decir?

Lagarto discreto

Respuestas:

$T$ $P$ $P$ $T$

Si. Para mostrar esto, daré un procedimiento para obtener el resultado aparentemente ligeramente más fuerte *:

$T$ $P$ $P$ $T$

$\Delta_0$ $v_0$ $T$ $v_0$ $Q$ $Q$

$v$
$w$ $AB$ $\Delta_v$ $D$ $AB$ $\Delta ABD$ $\Delta_w\leftarrow\Delta ABD$ $w$ $Q$

$P$ $T$

$AB$ $AD$

$CD$ $P$ $Q \notin \{B,D\}$ $DQ$ $P$ $AD$ $BD$ $\Delta ABD$ $Q$ existe solo si existe un punto análogo para el triángulo colocado anteriormente. Como no existe tal punto para el primer triángulo, esto significa que no existe tal punto para ningún triángulo que agreguemos.

$(X,Y)$ $P$ $XY$ $P$ $P$

Tenga en cuenta que los polígonos construidos en este método tienden a tener ángulos bastante agudos. Sospecho que los gráficos grandes arbitrarios requieren polígonos con ángulos pequeños arbitrarios, lo que podría ser un problema al dibujar estos polígonos con precisión finita.

_{*: La diferencia es que, si interpretamos 'único' como isomorfismo (que es consistente con la unicidad de las triangulaciones y los duales siendo diferentes), estaríamos bien con un polígono que tenga múltiples triangulaciones que tengan duales isomórficos. Sin embargo, es posible 'unir' más triángulos a esos polígonos para garantizar que algunos duales ya no sean isomorfos.}

Lagarto discreto
fuente