Distancia de giro

En matemáticas discretas e informática teórica , la distancia de inversión entre dos triangulaciones del mismo conjunto de puntos es el número de inversiones necesarias para transformar una triangulación en otra. Una inversión elimina una arista entre dos triángulos de la triangulación y luego añade la otra diagonal en el cuadrilátero que contiene dicha arista , formando así una triangulación diferente del mismo conjunto de puntos.

Se sabe que este problema es NP-difícil . Sin embargo, se desconoce la complejidad computacional de determinar la distancia de inversión entre polígonos convexos, un caso particular de este problema. Calcular la distancia de inversión entre triangulaciones de polígonos convexos también equivale a la distancia de rotación , que es el número de rotaciones necesarias para transformar un árbol binario en otro.

Dada una familia de triangulaciones de algún objeto geométrico, una inversión es una operación que transforma una triangulación en otra eliminando una arista entre dos triángulos y añadiendo la diagonal opuesta al cuadrilátero resultante. La distancia de inversión entre dos triangulaciones es el número mínimo de inversiones necesarias para transformar una triangulación en otra. ^{[ 1 ]} También se puede describir como la distancia del camino más corto en un grafo de inversión , un grafo que tiene un vértice por cada triangulación y una arista por cada inversión entre dos triangulaciones. ^{[ 1 ]} Las inversiones y las distancias de inversión se pueden definir de esta manera para varios tipos diferentes de triangulaciones, incluidas las triangulaciones de conjuntos de puntos en el plano euclidiano , las triangulaciones de polígonos y las triangulaciones de variedades abstractas . ^{[ 2 ]}

La distancia de inversión está bien definida solo si cualquier triangulación puede convertirse en cualquier otra triangulación mediante una secuencia de inversiones. Una condición equivalente es que el grafo de inversión debe estar conectado. ^{[ 3 ]}

En 1936, Klaus Wagner demostró que los grafos planares máximos en una esfera pueden transformarse en cualquier otro grafo planar máximo con los mismos vértices mediante un volteo. ^{[ 4 ]} AK Dewdney generalizó este resultado a triangulaciones en la superficie de un toro , mientras que Charles Lawson lo hizo a triangulaciones de un conjunto de puntos en un plano bidimensional. ^{[ 2 ] [ 5 ]}

Para triangulaciones de un conjunto de puntos en dimensión 5 o superior, existen ejemplos donde el grafo de inversión está desconectado y no se puede obtener una triangulación a partir de otras triangulaciones mediante inversiones. ^{[ 6 ] [ 3 ]} Si todos los grafos de inversión de conjuntos de puntos finitos de 3 o 4 dimensiones están conectados es un problema abierto . ^{[ 7 ]}

El número máximo de giros necesarios para transformar una triangulación en otra es el diámetro del gráfico de giro. El diámetro del gráfico de giro de una triangulación convexa${\displaystyle n}$-gon ha sido obtenido por Daniel Sleator , Robert Tarjan y William Thurston ^{[ 8 ]} cuando${\displaystyle n}$es suficientemente grande y por Lionel Pournin para todos${\displaystyle n}$Este diámetro es igual a${\displaystyle 2n-10}$cuando${\displaystyle n\geq 13}$. ^{[ 9 ]}

Se ha estudiado el diámetro de otros flip grafos. Por ejemplo, Klaus Wagner proporcionó una cota superior cuadrática para el diámetro del flip grafo de un conjunto de${\displaystyle n}$puntos no marcados en la esfera. ^{[ 4 ]} El límite superior actual del diámetro es${\displaystyle 5n-23}$, ^{[ 10 ]} mientras que el límite inferior más conocido es${\displaystyle 7n/3+\Theta (1)}$. ^{[ 11 ]} También se ha estudiado el diámetro de los gráficos de volteo de superficies topológicas arbitrarias con frontera y se conoce su valor exacto en varios casos. ^{[ 12 ] [ 13 ] [ 14 ]}

La distancia de giro entre triangulaciones de un polígono convexo es equivalente a la distancia de rotación entre dos árboles binarios. ^{[ 8 ]}

Calcular la distancia de giro entre triangulaciones de un conjunto de puntos es un problema NP-completo y APX-difícil . ^{[ 15 ] [ 16 ]} Sin embargo, es tratable con parámetros fijos (FPT), y se han propuesto varios algoritmos FPT que se ejecutan en tiempo exponencial. ^{[ 17 ] [ 18 ]}

Calcular la distancia de giro entre triangulaciones de un polígono simple también es NP-difícil. ^{[ 19 ]}

La complejidad del cálculo de la distancia de giro entre triangulaciones de un polígono convexo sigue siendo un problema abierto. ^{[ 20 ]}

Sea n el número de puntos en el conjunto de puntos y k la distancia de giro. El mejor algoritmo FPT actual se ejecuta en${\displaystyle O(n+k\cdot 32^{k})}$. ^{[ 17 ]} Existe un algoritmo FPT más rápido para la distancia de giro entre triangulaciones de polígonos convexos; tiene complejidad temporal${\displaystyle O(3.82^{k})}$. ^{[ 20 ]}

Si ningún conjunto de cinco puntos forma un pentágono vacío, existe un${\displaystyle O(n^{2})}$algoritmo para la distancia de volteo entre triangulaciones de este conjunto de puntos. ^{[ 1 ]}

• Asociaedro
• Voltear gráfico
• Distancia de rotación
• Celosía de Tamari