5 votos

Demuestra que las triangulaciones pueden transformarse unas en otras mediante el volteo de aristas.

Sea $\Delta_1$ y $\Delta_2$ sean dos triangulaciones del mismo conjunto de puntos $P_n$ . Demostrar que pueden transformarse entre sí mediante volteos de aristas. Para definir un giro de arista, sea $pqrs$ sean vértices (en el orden de las agujas del reloj) de un cuadrilátero. Si $pr$ es una arista de la triangulación, entonces $pr$ puede convertirse en $qs$ .

Para el caso de polígonos convexos, es fácil demostrar que existe una secuencia de volteo de aristas que aumentará el número de aristas comunes de dos triangulaciones diferentes. Pero estoy atascado en el caso general. ¿Alguna pista?

5voto

JiminyCricket Puntos 143

Otra forma de demostrarlo es utilizando las propiedades de optimización de la triangulación de Delaunay, que se tratan, por ejemplo, en este documento (sección 4.2) y esta presentación . Llamamos arista de una triangulación localmente Delaunay si forma parte del casco convexo o si la circunferencia de ninguno de los triángulos que la contiene contiene al tercer vértice del otro triángulo que la contiene. Entonces, cualquier arista que no sea localmente Delaunay puede sustituirse mediante un giro de arista por otra que sí lo sea. Además, si ordenamos las triangulaciones formando el vector de ángulos de vértice (todas las triangulaciones tienen el mismo número de triángulos y, por tanto, de ángulos de vértice), ordenándolo de forma ascendente y utilizando el orden lexicográfico en estos vectores ordenados, los giros de arista aumentan la triangulación respecto a este orden, ya que aumentan el ángulo mínimo en los triángulos que las contienen. Por tanto, el proceso debe terminar con una triangulación en la que todas las aristas sean localmente Delaunay. Esto implica las propiedades globales de Delaunay y, por tanto, la triangulación resultante es una triangulación de Delaunay. Cualquier triangulación de Delaunay puede transformarse en cualquier otra triangulación de Delaunay mediante volteos de aristas en los polígonos convexos alrededor de los vértices de Voronoi equidistantes de más de tres puntos. (Otra posibilidad es perturbar ligeramente los puntos para llevarlos a la posición general y hacer que la triangulación de Delaunay sea única y evitar así este caso especial). Así, hay una secuencia de volteos de aristas desde $\Delta_1$ a una triangulación de Delaunay a otra triangulación de Delaunay y de nuevo a $\Delta_2$ (utilizando la inversa de la secuencia de volteos de aristas necesaria para girar $\Delta_2$ en una triangulación de Delaunay).

0voto

user8269 Puntos 46

Creo que el problema está resuelto en Hurtado, Noy y Urrutia, Flipping edges on triangulations, en http://www.matem.unam.mx/urrutia/online_papers/Flipping.pdf

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X