Distancia de giro

Distancia de giro en triangulaciones

En matemáticas discretas y en informática teórica , la distancia de giro entre dos triangulaciones del mismo conjunto de puntos es el número de giros necesarios para transformar una triangulación en otra. Un giro elimina una arista entre dos triángulos de la triangulación y luego agrega la otra diagonal en el cuadrilátero que encierra la arista , formando una triangulación diferente del mismo conjunto de puntos.

Se sabe que este problema es NP-hard . Sin embargo, se desconoce la complejidad computacional de determinar la distancia de giro entre polígonos convexos, un caso especial de este problema. Calcular la distancia de giro entre triangulaciones de polígonos convexos también es equivalente a la distancia de rotación , la cantidad de rotaciones necesarias para transformar un árbol binario en otro.

Definición

Los gráficos invertidos de un pentágono y un hexágono

Dada una familia de triangulaciones de algún objeto geométrico, un giro es una operación que transforma una triangulación en otra eliminando una arista entre dos triángulos y agregando la diagonal opuesta al cuadrilátero resultante. La distancia de giro entre dos triangulaciones es el número mínimo de giros necesarios para transformar una triangulación en otra. ^[1] También se puede describir como la distancia de ruta más corta en un gráfico de giro , un gráfico que tiene un vértice para cada triangulación y una arista para cada giro entre dos triangulaciones. ^[1] Los giros y las distancias de giro 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]

Factibilidad

La distancia de volteo está bien definida solo si cualquier triangulación puede convertirse en cualquier otra triangulación mediante una secuencia de volteos. Una condición equivalente es que el gráfico de volteo debe estar conectado. ^[3]

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

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

Diámetro del gráfico invertido

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

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

Equivalencia con otros problemas

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

Complejidad computacional

Problema sin resolver en informática :

¿Cuál es la complejidad de calcular la distancia de giro entre dos triangulaciones de un polígono convexo?

(más problemas sin resolver en informática)

El cálculo de la distancia de inversión entre triangulaciones de un conjunto de puntos es tanto NP-completo como APX-difícil . ^{[15] [16]} Sin embargo, es manejable 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 de calcular la distancia de giro entre triangulaciones de un polígono convexo sigue siendo un problema abierto. ^[20]

Algoritmos

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

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

Véase también

• Asociaedro
• Gráfico invertido
• Distancia de rotación
• Celosía de tamari

Referencias

1. Eppstein, David (2010). "Finales felices para gráficos de rotación". Journal of Computational Geometry . 1 (1): Vol. 1 Núm. 1 (2010). doi :10.20382/JOCG.V1I1A2.
2. Dewdney, AK (1973). "Teorema de Wagner para grafos de toros". Matemáticas discretas . 4 (2). Elsevier BV: 139–149. doi : 10.1016/0012-365x(73)90076-9 . ISSN  0012-365X.
3. Santos, Francisco (2005-04-02). "Esquemas de Hilbert tóricos no conexos". Anales matemáticos . 332 (3). Springer Science and Business Media LLC: 645–665. arXiv : math/0204044 . doi :10.1007/s00208-005-0643-5. ISSN  0025-5831.
4. Wagner, K. (1936). "Bemerkungen zum Vierfarbenproblem". Jahresbericht der Deutschen Mathematiker-Vereinigung . 46 : 26–32. ISSN  0012-0456.
5. Lawson, Charles L. (1972). "Transformación de triangulaciones". Matemáticas discretas . 3 (4). Elsevier BV: 365–372. doi :10.1016/0012-365x(72)90093-3. ISSN  0012-365X.
6. Santos, Francisco (2000). "Un conjunto de puntos cuyo espacio de triangulaciones está desconectado". Revista de la American Mathematical Society . 13 (3). American Mathematical Society: 611–637. doi : 10.1090/S0894-0347-00-00330-1 . hdl : 10902/2584 . ISSN  0894-0347. JSTOR  2646121.
7. De Loera, Jesús A. ; Rambau, Jörg; Santos, Francisco (2010). Triangulaciones, estructuras para algoritmos y aplicaciones . Algoritmos y computación en matemáticas. Vol. 25. Springer.
8. Sleator, Daniel D.; Tarjan, Robert E .; Thurston, William P. (1988). "Distancia de rotación, triangulaciones y geometría hiperbólica". Revista de la American Mathematical Society . 1 (3). Sociedad Matemática Americana (AMS): 647–681. doi : 10.1090/s0894-0347-1988-0928904-4 . ISSN  0894-0347.
9. Pournin, Lionel (2014), "El diámetro de los asociaedros", Advances in Mathematics , 259 : 13–42, arXiv : 1207.6296 , doi : 10.1016/j.aim.2014.02.035 , MR  3197650
10. Cardinal, Jean; Hoffmann, Michael; Kusters, Vincent; Tóth, Csaba D.; Wettstein, Manuel (2018). "Diagramas de arco, distancias de inversión y triangulaciones hamiltonianas". Geometría computacional . 68 : 206–225. arXiv : 1611.02541 . doi : 10.1016/j.comgeo.2017.06.001 .
11. Frati, Fabrizio (2017). "Un límite inferior en el diámetro del gráfico de volteo". Revista electrónica de combinatoria . 24 (1): P1.43. arXiv : 1508.03473 . doi : 10.37236/5489 .
12. Parlier, Hugo; Pournin, Lionel (2017). "Espacios de módulos de flip-graph de superficies de relleno". Revista de la Sociedad Matemática Europea . 19 (9): 2697–2737. arXiv : 1407.1516 . doi : 10.4171/JEMS/726 .
13. Parlier, Hugo; Pournin, Lionel (2018). "Gráficos de rotación modulares de superficies con un solo agujero". Revista Europea de Combinatoria . 67 : 158–173. arXiv : 1510.07664 . doi : 10.1016/j.ejc.2017.07.003 .
14. Parlier, Hugo; Pournin, Lionel (2018). "Discos perforados una vez, polígonos no convexos y puntiedros". Anales de Combinatoria . 22 (3): 619–640. arXiv : 1602.04576 . doi :10.1007/s00026-018-0393-1.
15. Lubiw, Anna; Pathak, Vinayak (2015). "La distancia de inversión entre dos triangulaciones de un conjunto de puntos es NP-completa". Geometría computacional . 49 . Elsevier BV: 17–23. arXiv : 1205.2425 . doi : 10.1016/j.comgeo.2014.11.001 . ISSN  0925-7721.
16. Pilz, Alexander (2014). "La distancia de inversión entre triangulaciones de un conjunto de puntos planos es APX-hard". Geometría computacional . 47 (5). Elsevier BV: 589–604. arXiv : 1206.3179 . doi : 10.1016/j.comgeo.2014.01.001 . ISSN  0925-7721.
17. Feng, Qilong; Li, Shaohua; Meng, Xiangzhong; Wang, Jianxin (2021). "Un algoritmo FPT fpt2 para el problema de la distancia de volteo". Información y computación . 281 . Elsevier BV: 104708. arXiv : 1910.06185 . doi :10.1016/j.ic.2021.104708. ISSN  0890-5401.
18. Kanj, Iyad; Sedgwick, Eric; Xia, Ge (10 de febrero de 2017). "Cálculo de la distancia de giro entre triangulaciones". Geometría discreta y computacional . 58 (2). Springer Science and Business Media LLC: 313–344. arXiv : 1407.1525 . doi :10.1007/s00454-017-9867-x. ISSN  0179-5376.
19. Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (11 de junio de 2015). "La distancia de inversión entre triangulaciones de un polígono simple es NP-completa". Geometría discreta y computacional . 54 (2). Springer Science and Business Media LLC: 368–389. arXiv : 1209.0579 . doi :10.1007/s00454-015-9709-7. ISSN  0179-5376.
20. Li, Haohong; Xia, Ge (2023). "Un algoritmo FPT de tiempo 𝒪 (3,82 ^ k) para distancia de giro convexo". Schloss Dagstuhl - Leibniz-Zentrum für Informatik . doi : 10.4230/LIPICS.STACS.2023.44 . Consultado el 8 de noviembre de 2023 .