Fundamentos del Cálculo de la Deformación Temporal Dinámica Continua en 2D bajo Diferentes Normas

Información Básica

• ID del Artículo: 2511.20420
• Título: Fundamentos del Cálculo de la Deformación Temporal Dinámica Continua en 2D bajo Diferentes Normas
• Autores: Kevin Buchin (TU Dortmund), Maike Buchin (Ruhr University Bochum), Jan Erik Swiadek (Ruhr University Bochum), Sampson Wong (University of Copenhagen)
• Clasificación: cs.CG (Geometría Computacional)
• Fecha de Publicación/Conferencia: WALCOM 2026 (versión de preimpresión, enviada en noviembre de 2025)
• Enlace del Artículo: https://arxiv.org/abs/2511.20420

Resumen

La deformación temporal dinámica continua (CDTW) puede medir de manera robusta la similitud de curvas poligonales, siendo robusta frente a valores atípicos y tasas de muestreo variables. Sin embargo, el diseño y análisis de algoritmos CDTW enfrentan múltiples desafíos. Este artículo demuestra que bajo la norma euclidiana 2, la CDTW no puede calcularse exactamente utilizando únicamente operaciones algebraicas, y proporciona algoritmos exactos para calcular CDTW bajo normas que aproximan la norma 2. Estos últimos se basan en fundamentos técnicos establecidos por los autores que pueden generalizarse a normas arbitrarias y métricas relacionadas (como la similitud parcial de Fréchet).

Antecedentes de Investigación y Motivación

Problema de Investigación

Este artículo investiga cómo calcular de manera eficiente y exacta la distancia de deformación temporal dinámica continua (CDTW) entre curvas poligonales en el espacio bidimensional.

Importancia del Problema

1. Aplicaciones Prácticas Amplias: CDTW tiene aplicaciones importantes en verificación de firmas, emparejamiento de mapas, agrupamiento de trayectorias y otros campos
2. Superación de Limitaciones de Métodos Discretos: El DTW discreto tradicional ignora la continuidad de las curvas, produciendo resultados deficientes cuando las tasas de muestreo son diferentes o insuficientemente altas
3. Requisitos de Robustez: En comparación con la métrica de máximo valor de la distancia de Fréchet que es sensible a valores atípicos, CDTW utiliza integración de trayectorias, manejando mejor los valores atípicos

Limitaciones de Métodos Existentes

1. Métodos Aproximados y Heurísticos: Muchos métodos existentes manejan la integral discretizando las curvas de entrada, lo que hace que la calidad de la solución o el tiempo de ejecución dependan de la resolución de discretización
2. Restricciones Dimensionales: Los algoritmos exactos anteriores se limitaban principalmente al caso unidimensional, o solo tenían algoritmos de aproximación (1+ε) en tiempo pseudopolinómico bajo la norma euclidiana 2 en 2D
3. Comprensión Teórica Insuficiente: Las propiedades fundamentales de CDTW, particularmente bajo la norma 2 y diferentes normas en 2D, aún no se han comprendido completamente

Motivación de la Investigación

Los autores tienen como objetivo:

1. Comprender profundamente la complejidad computacional de CDTW, particularmente la no computabilidad bajo la norma 2
2. Establecer fundamentos técnicos aplicables a normas arbitrarias
3. Diseñar algoritmos exactos/aproximados que eviten la discretización de curvas

Contribuciones Principales

1. Teoría de Optimalidad Local (Sección 2): Demuestra que la definición de CDTW basada en integración de trayectorias permite coincidencias óptimas locales ventajosas desde la perspectiva algorítmica, y establece la existencia y métodos de cálculo de valles (valleys), aplicables a normas arbitrarias
2. Resultados de No Computabilidad (Sección 3): Demuestra que bajo la norma euclidiana 2, los valores numéricos involucrados en CDTW pueden ser números trascendentes, por lo que no pueden calcularse exactamente utilizando solo operaciones algebraicas (modelo ACMQ)
3. Algoritmo para Normas Poligonales (Sección 4): Propone un algoritmo exacto para calcular CDTW bajo normas con conjuntos de nivel unitario poligonales, que:
   • No requiere discretización de las curvas de entrada
   • Puede utilizarse para obtener aproximaciones (1+ε) bajo la norma 2
   • Utiliza normas poligonales regulares con k ∈ O(ε^(-1/2))
4. Propiedades Técnicas: Establece múltiples propiedades técnicas incluyendo continuidad de funciones óptimas, orden de propagación, etc., proporcionando fundamentos para análisis de complejidad

Explicación Detallada de Métodos

Definición de la Tarea

Entrada:

• Dos curvas poligonales bidimensionales P = ⟨p₀, ..., pₙ⟩ y Q = ⟨q₀, ..., qₘ⟩
• Norma ‖·‖

Salida:

• Valor CDTW cdtw‖·‖(P,Q)

Definición de CDTW (Definición 1): $\text{cdtw}_{\|\cdot\|}(P,Q) := \inf_{(f,g)\in\Pi(P)\times\Pi(Q)} \int_0^1 d(f(t), g(t)) \cdot \left\|\begin{pmatrix}\|f'(t)\| \\ \|g'(t)\|\end{pmatrix}\right\|_1 dt$

Donde:

• Π(P) contiene todas las parametrizaciones monótonas y continuamente diferenciables por partes de P
• d(·,·) es la función de distancia (este artículo utiliza d(p,q) = ‖p-q‖)
• Se utiliza la norma 1 para normalizar la velocidad, haciendo que la longitud de arco de la trayectoria sea σ = ‖P‖ + ‖Q‖

Marco Técnico Principal

1. Espacio de Parámetros y Trayectorias Óptimas (Sección 2)

Espacio de Parámetros (Definición 2): 0, ‖P‖ × 0, ‖Q‖, dividido en n×m celdas

Concepto de Valle (Definición 4):

• Un valle ℓ es una línea recta en el espacio de parámetros (pendiente ≠ -1)
• Cada punto z ∈ ℓ es un sumidero (sink): la función a lo largo de una línea con pendiente -1 alcanza su mínimo en z

Teorema Clave (Teorema 8): Para cualquier norma ‖·‖ y segmentos poligonales P, Q, existe un valle con pendiente positiva. Esto se demuestra mediante dualidad y análisis geométrico:

• Utiliza el Lema 7 para minimizar la función gauge en la línea
• Demuestra la existencia de un punto de maximización v* con componentes positivas
• Para normas poligonales, el valle puede calcularse en tiempo O(1) (Corolario 9)

Caracterización de Trayectorias Óptimas (Teorema 5): Dada un valle ℓ, la trayectoria óptima (x,y) se traza de la siguiente manera:

• Si ℓ intersecta el rectángulo Ξ = x₁,y₁×x₂,y₂, la trayectoria va de x a x̂ (en ℓ) a ŷ (en ℓ) a y
• En caso contrario, la trayectoria va de x a ξ a y, donde ξ es el punto en Ξ más cercano a ℓ

2. Resultado de Trascendencia (Sección 3)

Teorema Principal (Teorema 11): Construye curvas con vértices enteros P, Q tales que:

• (a) cdtw‖·‖₂(P,Q) es un número trascendente
• (b) Las coordenadas de los puntos de inflexión de cada trayectoria óptima son números trascendentes

Esquema de Prueba:

• Construye curvas específicas de dos segmentos P y tres segmentos Q
• Mediante cálculo integral obtiene el valor CDTW que contiene términos logarítmicos
• Utiliza el Teorema de Baker (resultado de teoría de números trascendentes, Lema 10) para demostrar que los números involucrados no son algebraicos
• Para (b), demuestra que los puntos que minimizan la derivada también son trascendentes

Significado: Esto demuestra que bajo la norma 2, CDTW no solo no puede expresarse mediante radicales, sino que ni siquiera es un número algebraico, por lo que ningún algoritmo exacto que utilice operaciones algebraicas puede existir.

3. Algoritmo para Normas Poligonales (Sección 4)

Marco del Algoritmo: Programación dinámica, propagando el costo de trayectorias óptimas a través de celdas del espacio de parámetros

Configuración de Normas:

• Utiliza normas Gψ(Rₖ) cuyo conjunto de nivel unitario 1-sublevel es ψ(Rₖ)
• Rₖ es un k-gono regular (k par), con vértices vᵣ = (cos(θᵣ), sin(θᵣ))ᵀ, θᵣ = r·2π/k
• ψ: ℝ² → ℝ² es un mapeo lineal biyectivo

Propiedades Clave (Lema 14):

• (a) Gψ(Rₖ) puede evaluarse en tiempo O(1), siendo lineal en cada cono
• (b) El espacio de propagación ΣA,B puede representarse mediante un arreglo de O(k) líneas, con optA,B siendo cuadrático en cada cara
• (c) La función óptima opt₀,B es cuadrática por partes

Proceso de Propagación (Algoritmo Propagate):

Entrada: Segmentos de curva P,Q, frontera B, funciones óptimas de 
         adyacencia y frontera opuesta
Salida: Función óptima de B (cuadrática por partes)

1. Calcular valle ℓ (tiempo O(1), Corolario 9)
2. Para cada frontera A ∈ {adj(B), opp(B)}:
   - Construir arreglo de O(k) líneas
   - Superponer con líneas verticales en puntos de ruptura de opt₀,A
   - Procesar intervalos en orden apropiado (Lema 15)
   - Para cada intervalo I:
     * Recopilar funciones candidatas en bordes y caras
     * Calcular envoltura inferior (tiempo O(Xᵢlog(Xᵢ)α(Xᵢ)))
     * Actualizar resultado usando pila
3. Retornar función óptima cuadrática por partes

Orden de Propagación (Lema 15): Se determina el orden correcto de propagación demostrando que los sufijos de trayectorias correspondientes no se cruzan:

• Si A y B tienen la misma dirección (como A = opp(B)), entonces s < s'
• Si A y B son ortogonales (como A = adj(B)), entonces s > s'

Garantía de Aproximación (Corolario 17):

• Utilizando normas k-gono regular Gψ(Rₖ) se puede calcular CDTW exactamente
• Se obtiene una aproximación (1+ε) bajo la norma 2 mediante k ∈ O(ε^(-1/2))
• Demostración: 1/cos(π/k)² ≤ 1+ε

Puntos de Innovación Técnica

1. Método de Dualidad Geométrica: Utiliza propiedades de dualidad de funciones gauge y geometría convexa para demostrar la existencia de valles y su propiedad de pendiente positiva
2. Aplicación de Teoría de Números Trascendentes: Primera aplicación del Teorema de Baker a CDTW, demostrando un resultado más fuerte que "no puede expresarse mediante radicales"
3. Evitar Discretización: Mediante la explotación de la naturaleza lineal por partes de normas poligonales, trabaja directamente en curvas continuas sin discretización
4. Programación Dinámica con Pila: Utiliza propiedades de orden de propagación (Lema 15) para acelerar el cálculo de envoltura inferior mediante estructuras de datos de pila
5. Marco Unificado: Los fundamentos técnicos establecidos son aplicables a normas arbitrarias y pueden generalizarse a métricas relacionadas (como similitud parcial de Fréchet)

Configuración Experimental

Nota: Este es un artículo de naturaleza teórica, cuyas contribuciones principales son algoritmos y análisis de complejidad, sin incluir experimentos en el sentido tradicional. El artículo se enfoca en:

• Demostraciones teóricas
• Corrección de algoritmos
• Análisis de complejidad

Verificación Teórica

1. Verificación de Trascendencia (Sección 3):
   • Construye ejemplos concretos para verificar el Teorema 11
   • Ejemplo (a): P = ⟨(1,2)ᵀ, (1,-4)ᵀ⟩, Q = ⟨(0,0)ᵀ, (5,0)ᵀ⟩
   • Cálculo resultante: cdtw = ½·ln(α₁) - 1/√2 - ½·ln(α₂) + √5 + 17√2
   • Donde α₁ = √2-1, α₂ = √5-2
   • Se demuestra mediante el Lema 10 que esto es un número trascendente
2. Corrección del Algoritmo:
   • El Teorema 16 demuestra la corrección del algoritmo Propagate
   • El Teorema 20 demuestra la continuidad de la función óptima
   • El Lema 19 demuestra la convergencia de la secuencia de trayectorias

Análisis de Complejidad

Tiempo de Ejecución (Proposición 18):

• Tiempo total: O(N·k²log(k)α(k))
• N: número total de fragmentos cuadráticos en todas las funciones óptimas
• α: función inversa de Ackermann

Problemas Sin Resolver:

• En el caso 1D se ha demostrado que N ∈ O(n⁵)
• En el caso 2D aún no se ha establecido una cota polinómica para N
• Dificultad principal: las líneas de pendiente negativa en el arreglo pueden causar comportamiento de duplicación (Figura 5)

Resultados Experimentales

Resumen de Resultados Teóricos

1. No Computabilidad:
   • Demuestra explícitamente que CDTW bajo la norma 2 involucra números trascendentes
   • Descarta la posibilidad de algoritmos puramente algebraicos
   • Proporciona apoyo teórico para algoritmos aproximados
2. Validez del Algoritmo:
   • Cálculo exacto posible bajo normas poligonales
   • Obtención de aproximación (1+ε) de la norma 2, con k = O(ε^(-1/2))
   • No requiere discretización de curvas de entrada
3. Generalidad:
   • La existencia de valles es aplicable a todas las normas
   • El marco técnico puede generalizarse a otras métricas

Análisis de Casos

Ejemplo 1 (Figura 4, Teorema 11a):

• Curvas simples de 2 segmentos y 1 segmento
• Celda única del espacio de parámetros
• La trayectoria óptima tiene 3 segmentos: dos en el valle, uno horizontal
• El valor CDTW contiene términos logarítmicos, demostrándose que es trascendente

Ejemplo 2 (Figura 4, Teorema 11b):

• Curvas de 3 segmentos y 1 segmento
• Dos celdas del espacio de parámetros
• La trayectoria óptima candidata γₛ se parametriza como s ∈ 0,10
• Mediante análisis de soluciones de C'(s) = 0, se demuestra que el punto minimizador s* es trascendente
• Verificación numérica: s* ≈ 2.08, mientras que el único candidato algebraico s₀* ≈ 4.31

Trabajo Relacionado

DTW y Distancia de Fréchet

• DTW Estándar: Tiempo O(n²) Vintsyuk 1968
• Distancia de Fréchet: Tiempo O(n²log n) Alt & Godau 1995
• Cotas Mejoradas: Existen límites superiores mejores Gold & Sharir 2018; Buchin et al. 2017; Cheng & Huang 2025

Variantes de DTW Continuo

• Serra & Berthod 1994: Primera versión continua, coincidencia continua pero suma finita
• Munich & Perona 1999: Definición equivalente y análisis
• Serra & Berthod 1995: Versión invariante a traslación basada en cambios de vector de distancia
• Efrat et al. 2007: Versión integral más general
• Buchin 2007: Definición adoptada en este artículo

Algoritmos Exactos y Aproximados

• Klaren 2020, Buchin et al. 2022: Algoritmo exacto en tiempo polinómico para 1D
• Maheshwari et al. 2018: Aproximación (1+ε) en tiempo pseudopolinómico para norma euclidiana 2 en 2D
• Brankovic 2022: Algoritmo para norma 1 en 2D

Resultados de No Computabilidad

• De Carufel et al. 2014: La similitud parcial de Fréchet no puede calcularse mediante radicales
• Bajaj 1988, De Carufel et al. 2014: Grado algebraico de problemas de optimización geométrica relacionados
• Este Artículo: Resultado de trascendencia más fuerte

Métricas Relacionadas

• Distancia de Fréchet Lexicográfica Rote 2014
• Similitud Parcial de Fréchet Buchin et al. 2009
• Estas métricas comparten propiedades de optimalidad local con CDTW

Conclusiones y Discusión

Conclusiones Principales

1. Contribuciones Teóricas:
   • Bajo la norma 2, el cálculo exacto de CDTW requiere números trascendentes, más allá del modelo de cálculo algebraico
   • Bajo cualquier norma existe un valle con pendiente positiva, garantizando la viabilidad del diseño de algoritmos
   • Se establece un marco técnico aplicable a normas arbitrarias
2. Contribuciones de Algoritmos:
   • Proporciona un algoritmo exacto bajo normas poligonales
   • Obtiene aproximación (1+ε) de la norma 2 mediante k-gonos regulares con k = O(ε^(-1/2))
   • Evita la discretización de curvas de entrada
3. Problemas Abiertos:
   • Aún no se ha establecido una cota de tiempo polinómico para el caso 2D
   • El desafío principal es el comportamiento de duplicación causado por líneas de pendiente negativa en el arreglo

Limitaciones

1. Análisis de Complejidad Incompleto:
   • Aunque se proporciona una cota O(N·k²log(k)α(k)), no se ha establecido una cota polinómica para N
   • La técnica de análisis O(n⁵) en 1D no se generaliza directamente a 2D
2. Eficiencia Práctica No Verificada:
   • El artículo es puramente teórico, sin implementación ni evaluación experimental
   • El tiempo de ejecución real puede verse significativamente afectado por k y N
3. Dependencia del Factor de Aproximación:
   • k = O(ε^(-1/2)) significa que ε pequeño requiere k grande
   • Por ejemplo, ε = 0.01 requiere k ≈ 314
4. Estabilidad Numérica:
   • Aunque se evita el cálculo exacto de números trascendentes, los problemas de error acumulativo persisten (mencionado en Sección 3)

Direcciones Futuras

1. Análisis de Complejidad:
   • Resolver el problema de la cota polinómica para N en el caso 2D
   • Particularmente, abordar el comportamiento de duplicación en la Figura 5
2. Implementación Práctica:
   • Implementar el algoritmo y realizar evaluación experimental
   • Comparar con métodos de discretización existentes
3. Aplicaciones Generalizadas:
   • Generalizar técnicas a métricas relacionadas como similitud parcial de Fréchet
   • Explorar otros campos de aplicación
4. Mejora de Aproximación:
   • Investigar si se puede obtener la misma garantía de aproximación con k más pequeño
   • Explorar estrategias de aproximación alternativas

Evaluación Profunda

Fortalezas

1. Profundidad Teórica:
   • El resultado de trascendencia es una contribución teórica importante en el campo, más fuerte que "no puede expresarse mediante radicales"
   • La técnica de prueba utilizando el Teorema de Baker es novedosa y rigurosa
   • La demostración geométrica de la existencia de valles es elegante y general
2. Rigor Técnico:
   • Todos los teoremas tienen demostraciones completas (en el texto principal o apéndice)
   • Las derivaciones matemáticas son detalladas, especialmente la prueba detallada de trascendencia en el Apéndice B
   • Se consideran múltiples casos límite
3. Generalidad:
   • El marco establecido es aplicable a normas arbitrarias
   • Puede generalizarse a métricas relacionadas (distancia de Fréchet lexicográfica, similitud parcial de Fréchet)
   • Resultados como el Teorema 8 y Lema 15 tienen valor independiente
4. Diseño de Algoritmos:
   • Evitar la discretización es una contribución metodológica importante
   • La propagación con pila aprovecha la estructura geométrica del problema
   • El algoritmo Propagate está bien diseñado y es fácil de entender
5. Calidad de Escritura:
   • La estructura es clara, progresando desde motivación a teoría a algoritmo
   • Las ilustraciones (Figuras 1-9) facilitan la comprensión
   • La revisión de trabajo relacionado es completa

Deficiencias

1. Ausencia de Experimentos:
   • Como artículo de algoritmos, carece de implementación real y evaluación experimental
   • No es posible evaluar la eficiencia práctica y usabilidad del algoritmo
   • Faltan comparaciones de rendimiento real con métodos existentes
2. Complejidad No Completamente Resuelta:
   • La cota polinómica para N es un problema abierto clave
   • No hay una dirección clara para resolver el comportamiento de duplicación
   • Esto limita la completitud teórica del algoritmo
3. Parámetros de Aproximación:
   • La dependencia k = O(ε^(-1/2)) es relativamente débil
   • ε pequeño requiere k grande, lo que puede afectar la eficiencia práctica
   • No se discute el impacto de valores reales de k en el rendimiento
4. Problemas Numéricos:
   • Aunque se evita el cálculo de números trascendentes, el problema de error acumulativo mencionado en Sección 3 no se discute suficientemente
   • No se analiza la estabilidad numérica de funciones cuadráticas por partes
5. Discusión de Aplicaciones:
   • La discusión de escenarios de aplicación práctica es limitada
   • No se discute cuándo se debe usar CDTW en lugar de DTW o distancia de Fréchet

Impacto

1. Impacto Teórico:
   • El resultado de trascendencia es un avance importante en la complejidad computacional de métricas de similitud de curvas
   • Proporciona una base teórica sólida para la necesidad de algoritmos aproximados
   • El marco técnico puede inspirar investigación en problemas relacionados
2. Valor Práctico:
   • El algoritmo de aproximación (1+ε) tiene valor para aplicaciones prácticas
   • Evitar la discretización puede mejorar la calidad de la solución
   • Pero la eficiencia real necesita verificación experimental
3. Reproducibilidad:
   • La descripción del algoritmo es detallada, teóricamente reproducible
   • Pero faltan detalles de implementación y código
   • Las demostraciones detalladas en el Apéndice facilitan la comprensión
4. Investigación Posterior:
   • Los problemas abiertos de complejidad proporcionan direcciones claras para investigación posterior
   • El marco técnico puede generalizarse a otras métricas y aplicaciones
   • Puede inspirar nuevas ideas de diseño de algoritmos

Escenarios de Aplicabilidad

1. Investigación Teórica:
   • Investigación de complejidad computacional de métricas de similitud de curvas
   • Diseño de algoritmos para problemas de optimización geométrica
   • Aplicaciones de números trascendentes en geometría computacional
2. Aplicaciones Prácticas (Potenciales):
   • Análisis de similitud de trayectorias (cuando hay gran diferencia en tasas de muestreo)
   • Verificación de firmas (requiere robustez frente a valores atípicos)
   • Emparejamiento de mapas (emparejamiento de trayectorias GPS)
   • Agrupamiento de series temporales
3. Escenarios No Aplicables:
   • Aplicaciones que requieren cálculo en tiempo real (complejidad relativamente alta)
   • Datos de alta dimensión (actualmente limitado a 2D)
   • Aplicaciones donde no se requiere alta precisión (DTW podría ser suficiente)

Referencias

Referencias Clave

1. Alt & Godau 1995: Algoritmo clásico para distancia de Fréchet
2. Vintsyuk 1968: Definición original de DTW
3. Baker 1990: Fundamentos de teoría de números trascendentes (fuente del Lema 10)
4. Buchin 2007: Fuente de la definición de CDTW
5. Buchin, Nusser & Wong 2022: Algoritmo exacto para CDTW en 1D
6. Maheshwari, Sack & Scheffer 2018: Algoritmo aproximado para CDTW en 2D
7. Brankovic 2022: Algoritmo para norma 1 en 2D

Fundamentos Teóricos

8. Boyd & Vandenberghe 2009: Optimización convexa (funciones gauge)
9. Schaefer & Wolff 1999: Espacios vectoriales topológicos (teoría de normas)
10. De Carufel et al. 2014: No computabilidad de similitud parcial de Fréchet

Evaluación General: Este es un artículo de alta calidad en geometría computacional teórica, haciendo contribuciones importantes en complejidad computacional y diseño de algoritmos para CDTW. El resultado de trascendencia es un avance revolucionario en el campo, y el marco técnico tiene buena generalidad. Las principales deficiencias son la ausencia de evaluación experimental y análisis de complejidad incompleto. El artículo es apropiado para publicación en conferencias de primer nivel en geometría computacional (como WALCOM, SoCG), y tiene importante valor de referencia tanto para investigadores teóricos como para aquellos interesados en métricas de similitud de curvas.