Fondamentaux du Calcul de la Déformation Temporelle Dynamique Continue en 2D sous Différentes Normes

Informations Fondamentales

• ID de l'article: 2511.20420
• Titre: Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms
• Auteurs: Kevin Buchin (TU Dortmund), Maike Buchin (Ruhr University Bochum), Jan Erik Swiadek (Ruhr University Bochum), Sampson Wong (University of Copenhagen)
• Classification: cs.CG (Géométrie Computationnelle)
• Date de publication/Conférence: WALCOM 2026 (version de préimpression, soumise en novembre 2025)
• Lien de l'article: https://arxiv.org/abs/2511.20420

Résumé

La déformation temporelle dynamique continue (CDTW) permet de mesurer robustement la similarité des courbes polygonales, avec une robustesse aux valeurs aberrantes et aux taux d'échantillonnage. Cependant, la conception et l'analyse des algorithmes CDTW font face à de multiples défis. Cet article démontre que sous la norme euclidienne 2, il est impossible de calculer exactement la CDTW en utilisant uniquement des opérations algébriques, et fournit un algorithme exact pour calculer la CDTW sous des normes qui approximent la norme 2. Ce dernier repose sur les fondations techniques établies par les auteurs, qui peuvent être généralisées à des normes arbitraires et à des métriques connexes (telles que la similarité partielle de Fréchet).

Contexte et Motivation de la Recherche

Problème de Recherche

Cet article étudie comment calculer efficacement et exactement la distance de déformation temporelle dynamique continue (CDTW) entre des courbes polygonales dans l'espace bidimensionnel.

Importance du Problème

1. Applications pratiques étendues: La CDTW a des applications importantes dans la vérification de signatures, l'appariement cartographique, le clustering de trajectoires et autres domaines
2. Surmonter les limitations des méthodes discrètes: La DTW discrète traditionnelle ignore la continuité des courbes, produisant de mauvais résultats lorsque les taux d'échantillonnage diffèrent ou sont insuffisants
3. Exigences de robustesse: Comparée à la distance de Fréchet qui est sensible aux valeurs aberrantes avec sa métrique de valeur maximale, la CDTW utilise l'intégration de chemin et gère mieux les valeurs aberrantes

Limitations des Méthodes Existantes

1. Méthodes approximatives et heuristiques: De nombreuses méthodes existantes traitent l'intégrale en discrétisant les courbes d'entrée, ce qui rend la qualité de la solution ou le temps d'exécution dépendant de la résolution de discrétisation
2. Restrictions dimensionnelles: Les algorithmes exacts précédents étaient principalement limités au cas unidimensionnel, ou ne disposaient que d'algorithmes d'approximation (1+ε) en temps pseudo-polynomial pour la norme euclidienne 2 en 2D
3. Compréhension théorique insuffisante: Les propriétés fondamentales de la CDTW, en particulier en 2D et sous différentes normes, n'ont pas été suffisamment comprises

Motivation de la Recherche

Les auteurs visent à:

1. Approfondir la compréhension de la complexité computationnelle de la CDTW, en particulier l'incalculabilité sous la norme 2
2. Établir des fondations techniques applicables à des normes arbitraires
3. Concevoir des algorithmes exacts/approximatifs qui évitent la discrétisation des courbes

Contributions Principales

1. Théorie de l'optimalité locale (Section 2): Démontre que la définition de la CDTW basée sur l'intégration de chemin permet des appariements localement optimaux avantageux du point de vue algorithmique, et établit l'existence et les méthodes de calcul des vallées, applicables à des normes arbitraires
2. Résultats d'incalculabilité (Section 3): Démontre que sous la norme euclidienne 2, les valeurs impliquées dans la CDTW peuvent être des nombres transcendantaux, et ne peuvent donc pas être calculées exactement en utilisant uniquement des opérations algébriques (modèle ACMQ)
3. Algorithme pour normes polygonales (Section 4): Propose un algorithme exact pour calculer la CDTW sous des normes avec ensembles de niveau polygonaux, qui:
   • Ne nécessite pas de discrétisation des courbes d'entrée
   • Peut être utilisé pour obtenir une approximation (1+ε) sous la norme 2
   • Utilise des normes polygonales régulières avec k ∈ O(ε^(-1/2))
4. Propriétés techniques: Établit plusieurs propriétés techniques incluant la continuité des fonctions optimales, l'ordre de propagation, etc., posant les fondations pour l'analyse de complexité

Explication Détaillée de la Méthode

Définition de la Tâche

Entrée:

• Deux courbes polygonales bidimensionnelles P = ⟨p₀, ..., pₙ⟩ et Q = ⟨q₀, ..., qₘ⟩
• Une norme ‖·‖

Sortie:

• La valeur CDTW cdtw‖·‖(P,Q)

Définition de la CDTW (Définition 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$

où:

• Π(P) contient toutes les paramétrages monotones et continus par morceaux différentiables de P
• d(·,·) est la fonction de distance (cet article utilise d(p,q) = ‖p-q‖)
• La norme 1 est utilisée pour normaliser les vitesses, rendant la longueur d'arc du chemin σ = ‖P‖ + ‖Q‖

Cadre Technique Principal

1. Espace de Paramètres et Chemins Optimaux (Section 2)

Espace de paramètres (Définition 2): 0, ‖P‖ × 0, ‖Q‖, divisé en n×m cellules

Concept de vallée (Définition 4):

• Une vallée ℓ est une ligne droite dans l'espace de paramètres (pente ≠ -1)
• Chaque point z ∈ ℓ est un puits (sink): la fonction le long d'une ligne de pente -1 atteint son minimum en z

Théorème clé (Théorème 8): Pour toute norme ‖·‖ et segments polygonaux P, Q, il existe une vallée de pente positive. Ceci est démontré par dualité et analyse géométrique:

• Utilise le Lemme 7 pour minimiser la fonction de jauge sur la ligne
• Démontre l'existence d'un point de maximisation v* avec composantes positives
• Pour les normes polygonales, la vallée peut être calculée en temps O(1) (Corollaire 9)

Caractérisation du chemin optimal (Théorème 5): Étant donnée une vallée ℓ, le chemin optimal (x,y) se trace de la manière suivante:

• Si ℓ intersecte le rectangle Ξ = x₁,y₁×x₂,y₂, le chemin va de x à x̂ (sur ℓ) à ŷ (sur ℓ) à y
• Sinon, le chemin va de x à ξ à y, où ξ est le point de Ξ le plus proche de ℓ

2. Résultat de Transcendance (Section 3)

Théorème principal (Théorème 11): Construit des courbes P, Q avec sommets entiers telles que:

• (a) cdtw‖·‖₂(P,Q) est un nombre transcendantal
• (b) Les coordonnées des points de virage de chaque chemin optimal sont des nombres transcendantaux

Esquisse de la preuve:

• Construit des courbes spécifiques: P avec deux segments et Q avec trois segments
• Calcule la CDTW par intégration, obtenant une valeur contenant des termes logarithmiques
• Utilise le théorème de Baker (résultat de la théorie des nombres transcendantaux, Lemme 10) pour prouver que les nombres impliqués ne sont pas algébriques
• Pour (b), démontre que le point minimisant la dérivée est également transcendantal

Signification: Ceci montre que sous la norme 2, la CDTW n'est pas seulement incalculable par radicaux, mais n'est même pas un nombre algébrique. Par conséquent, aucun algorithme exact utilisant des opérations algébriques n'existe.

3. Algorithme pour Normes Polygonales (Section 4)

Cadre algorithmique: Programmation dynamique, propageant le coût du chemin optimal à travers les cellules de l'espace de paramètres

Définition de la norme:

• Utilise une norme Gψ(Rₖ) dont l'ensemble de niveau 1-sublevel est ψ(Rₖ)
• Rₖ est un k-gon régulier (k pair), avec sommets vᵣ = (cos(θᵣ), sin(θᵣ))ᵀ, θᵣ = r·2π/k
• ψ: ℝ² → ℝ² est une application linéaire bijective

Propriétés clés (Lemme 14):

• (a) Gψ(Rₖ) peut être évaluée en temps O(1), linéaire sur chaque cône
• (b) L'espace de propagation ΣA,B peut être représenté par un arrangement de O(k) lignes, optA,B est quadratique sur chaque face
• (c) La fonction optimale opt₀,B est par morceaux quadratique

Processus de propagation (Algorithme Propagate):

Entrée: segments de courbe P,Q, limite B, fonctions optimales 
        des limites adjacentes et opposées
Sortie: fonction optimale pour B (par morceaux quadratique)

1. Calculer la vallée ℓ (temps O(1), Corollaire 9)
2. Pour chaque limite A ∈ {adj(B), opp(B)}:
   - Construire un arrangement de O(k) lignes
   - Superposer avec les lignes verticales aux points de rupture de opt₀,A
   - Traiter les intervalles dans l'ordre approprié (Lemme 15)
   - Pour chaque intervalle I:
     * Collecter les fonctions candidates sur les arêtes et faces
     * Calculer l'enveloppe inférieure (temps O(Xᵢlog(Xᵢ)α(Xᵢ)))
     * Mettre à jour le résultat en utilisant une pile
3. Retourner la fonction optimale par morceaux quadratique

Ordre de propagation (Lemme 15): Détermine l'ordre de propagation correct en prouvant que les suffixes des chemins correspondants ne s'entrecroisent pas:

• Si A et B sont dans la même direction (par exemple A = opp(B)), alors s < s'
• Si A et B sont orthogonaux (par exemple A = adj(B)), alors s > s'

Garantie d'approximation (Corollaire 17):

• Utiliser la norme k-gon régulière Gψ(Rₖ) calcule exactement la CDTW
• Obtenir une approximation (1+ε) sous la norme 2 avec k ∈ O(ε^(-1/2))
• Preuve: 1/cos(π/k)² ≤ 1+ε

Points d'Innovation Technique

1. Méthode de dualité géométrique: Utilise les propriétés de dualité des fonctions de jauge et la géométrie convexe pour prouver l'existence et la positivité de la pente des vallées
2. Application de la théorie des nombres transcendantaux: Première application du théorème de Baker à la CDTW, prouvant un résultat plus fort que "ne peut pas être exprimé par radicaux"
3. Éviter la discrétisation: En exploitant la linéarité par morceaux des normes polygonales, travaille directement sur les courbes continues sans discrétisation
4. Programmation dynamique basée sur pile: Utilise les propriétés d'ordre de propagation (Lemme 15) et une structure de données de pile pour accélérer le calcul de l'enveloppe inférieure
5. Cadre unifié: Les fondations techniques établies s'appliquent à des normes arbitraires et peuvent être généralisées à des métriques connexes (telles que la similarité partielle de Fréchet)

Configuration Expérimentale

Remarque: Cet article est un article théorique dont les contributions principales sont l'algorithme et l'analyse de complexité, sans partie expérimentale au sens traditionnel. L'article se concentre sur:

• Preuves théoriques
• Correction algorithmique
• Analyse de complexité

Vérification Théorique

1. Vérification de transcendance (Section 3):
   • Construit des exemples concrets pour vérifier le Théorème 11
   • Exemple (a): P = ⟨(1,2)ᵀ, (1,-4)ᵀ⟩, Q = ⟨(0,0)ᵀ, (5,0)ᵀ⟩
   • Calcul obtenu: cdtw = ½·ln(α₁) - 1/√2 - ½·ln(α₂) + √5 + 17√2
   • où α₁ = √2-1, α₂ = √5-2
   • Prouve via le Lemme 10 que c'est un nombre transcendantal
2. Correction algorithmique:
   • Le Théorème 16 prouve la correction de l'algorithme Propagate
   • Le Théorème 20 prouve la continuité de la fonction optimale
   • Le Lemme 19 prouve la convergence de la séquence de chemins

Analyse de Complexité

Temps d'exécution (Proposition 18):

• Temps total: O(N·k²log(k)α(k))
• N: nombre total de segments quadratiques de toutes les fonctions optimales
• α: fonction inverse d'Ackermann

Problèmes non résolus:

• En 1D, il a été prouvé que N ∈ O(n⁵)
• En 2D, une borne polynomiale pour N n'a pas encore été établie
• Difficulté principale: les lignes de pente négative dans l'arrangement peuvent entraîner un comportement de doublement (Figure 5)

Résultats Expérimentaux

Résumé des Résultats Théoriques

1. Incalculabilité:
   • Démontre explicitement que la CDTW sous la norme 2 implique des nombres transcendantaux
   • Exclut la possibilité d'algorithmes purement algébriques
   • Fournit un soutien théorique aux algorithmes d'approximation
2. Efficacité algorithmique:
   • Calcul exact possible sous normes polygonales
   • Obtient une approximation (1+ε) de la norme 2 avec k = O(ε^(-1/2))
   • Pas besoin de discrétiser les courbes d'entrée
3. Généralité:
   • L'existence de vallées s'applique à toutes les normes
   • Le cadre technique peut être généralisé à d'autres métriques

Analyse de Cas

Exemple 1 (Figure 4, Théorème 11a):

• Courbes simples: 2 segments et 1 segment
• Cellule unique de l'espace de paramètres
• Le chemin optimal a 3 segments: deux sur la vallée, un horizontal
• La valeur CDTW contient un terme logarithmique, prouvée transcendantale

Exemple 2 (Figure 4, Théorème 11b):

• Courbes: 3 segments et 1 segment
• Deux cellules de l'espace de paramètres
• Le chemin optimal candidat γₛ est paramétré par s ∈ 0,10
• En analysant les solutions de C'(s) = 0, prouve que le point minimisant s* est transcendantal
• Vérification numérique: s* ≈ 2.08, tandis que l'unique candidat algébrique s₀* ≈ 4.31

Travaux Connexes

DTW et Distance de Fréchet

• DTW standard: Temps O(n²) Vintsyuk 1968
• Distance de Fréchet: Temps O(n²log n) Alt & Godau 1995
• Bornes améliorées: Existent de meilleures bornes supérieures Gold & Sharir 2018; Buchin et al. 2017; Cheng & Huang 2025

Variantes de DTW Continu

• Serra & Berthod 1994: Première version continue, appariement continu mais somme finie
• Munich & Perona 1999: Définition équivalente et analyse
• Serra & Berthod 1995: Version invariante par translation basée sur les changements de vecteur de distance
• Efrat et al. 2007: Version intégrale plus générale
• Buchin 2007: Définition adoptée dans cet article

Algorithmes Exacts et Approximatifs

• Klaren 2020, Buchin et al. 2022: Algorithme exact en temps polynomial pour 1D
• Maheshwari et al. 2018: Approximation (1+ε) en temps pseudo-polynomial pour norme euclidienne 2 en 2D
• Brankovic 2022: Algorithme pour norme 1 en 2D

Résultats d'Incalculabilité

• De Carufel et al. 2014: La similarité partielle de Fréchet ne peut pas être calculée par radicaux
• Bajaj 1988, De Carufel et al. 2014: Degré algébrique de problèmes d'optimisation géométrique connexes
• Cet article: Résultat de transcendance plus fort

Métriques Connexes

• Distance de Fréchet lexicographique Rote 2014
• Similarité partielle de Fréchet Buchin et al. 2009
• Ces métriques partagent les propriétés d'optimalité locale avec la CDTW

Conclusion et Discussion

Conclusions Principales

1. Contributions théoriques:
   • Sous la norme 2, le calcul exact de la CDTW nécessite des nombres transcendantaux, dépassant le modèle de calcul algébrique
   • Une vallée de pente positive existe sous toute norme, garantissant la faisabilité de la conception algorithmique
   • Les fondations techniques établies s'appliquent à des normes arbitraires
2. Contributions algorithmiques:
   • Fournit un algorithme exact sous normes polygonales
   • Obtient une approximation (1+ε) de la norme 2 via des k-gons réguliers avec k = O(ε^(-1/2))
   • Évite la discrétisation des courbes d'entrée
3. Problèmes ouverts:
   • Une borne polynomiale en 2D n'a pas encore été établie
   • Le défi principal est le comportement de doublement potentiel causé par les lignes de pente négative dans l'arrangement

Limitations

1. Analyse de complexité incomplète:
   • Bien qu'une borne O(N·k²log(k)α(k)) soit donnée, la borne polynomiale pour N n'est pas établie
   • La technique d'analyse O(n⁵) en 1D ne se généralise pas directement à 2D
2. Efficacité pratique non vérifiée:
   • L'article est purement théorique, sans implémentation ni évaluation expérimentale
   • Le temps d'exécution réel peut être fortement affecté par k et N
3. Dépendance du facteur d'approximation:
   • k = O(ε^(-1/2)) signifie que petit ε nécessite grand k
   • Par exemple, ε = 0.01 nécessite k ≈ 314
4. Stabilité numérique:
   • Bien que le calcul exact de nombres transcendantaux soit évité, les problèmes d'erreur d'accumulation persistent (mentionnés en Section 3)

Directions Futures

1. Analyse de complexité:
   • Résoudre le problème de la borne polynomiale pour N en 2D
   • Traiter particulièrement le comportement de doublement de la Figure 5
2. Implémentation pratique:
   • Implémenter l'algorithme et effectuer une évaluation expérimentale
   • Comparer avec les méthodes de discrétisation existantes
3. Applications généralisées:
   • Généraliser la technique à la similarité partielle de Fréchet et autres métriques connexes
   • Explorer d'autres domaines d'application
4. Amélioration de l'approximation:
   • Étudier si une approximation similaire peut être obtenue avec k plus petit
   • Explorer d'autres stratégies d'approximation

Évaluation Approfondie

Avantages

1. Profondeur théorique:
   • Le résultat de transcendance est une contribution théorique importante dans ce domaine, plus fort que "ne peut pas être exprimé par radicaux"
   • La technique de preuve utilisant le théorème de Baker est nouvelle et rigoureuse
   • La preuve géométrique de l'existence de vallées est élégante et générale
2. Rigueur technique:
   • Tous les théorèmes ont des preuves complètes (texte principal ou appendice)
   • Les dérivations mathématiques sont détaillées, particulièrement la preuve détaillée de transcendance en Appendice B
   • Les cas limites multiples sont considérés
3. Généralité:
   • Le cadre établi s'applique à des normes arbitraires
   • Peut être généralisé à des métriques connexes (distance de Fréchet lexicographique, similarité partielle de Fréchet)
   • Les résultats comme le Théorème 8 et le Lemme 15 ont une valeur indépendante
4. Conception algorithmique:
   • Éviter la discrétisation est une contribution méthodologique importante
   • La propagation basée sur pile exploite la structure géométrique du problème
   • L'algorithme Propagate est clairement conçu et facile à comprendre
5. Qualité de rédaction:
   • Structure claire, progressant de la motivation à la théorie à l'algorithme
   • Les illustrations (Figures 1-9) aident à la compréhension
   • L'examen des travaux connexes est complet

Insuffisances

1. Absence d'expériences:
   • En tant qu'article algorithmique, manque d'implémentation réelle et d'évaluation expérimentale
   • Impossible d'évaluer l'efficacité réelle et l'utilisabilité de l'algorithme
   • Manque de comparaison de performance réelle avec les méthodes existantes
2. Complexité non complètement résolue:
   • La borne polynomiale pour N est un problème ouvert clé
   • Pas de direction claire pour résoudre le comportement de doublement
   • Cela limite l'intégrité théorique de l'algorithme
3. Paramètres d'approximation:
   • La dépendance k = O(ε^(-1/2)) est relativement faible
   • Petit ε nécessite grand k, pouvant affecter l'efficacité pratique
   • Pas de discussion sur l'impact de k réel sur la performance
4. Problèmes numériques:
   • Bien que le calcul de nombres transcendantaux soit évité, le problème d'erreur d'accumulation mentionné en Section 3 n'est pas suffisamment discuté
   • La stabilité numérique des fonctions quadratiques par morceaux n'est pas analysée
5. Discussion d'application:
   • Discussion limitée des scénarios d'application pratique
   • Pas de discussion sur quand utiliser CDTW plutôt que DTW ou distance de Fréchet

Impact

1. Impact théorique:
   • Le résultat de transcendance est un progrès important dans la complexité computationnelle des métriques de similarité de courbes
   • Fournit une base théorique solide pour la nécessité des algorithmes d'approximation
   • Le cadre technique peut inspirer la recherche sur des problèmes connexes
2. Valeur pratique:
   • L'algorithme d'approximation (1+ε) a de la valeur pour les applications pratiques
   • Éviter la discrétisation peut améliorer la qualité de la solution
   • Mais l'efficacité réelle nécessite une vérification expérimentale
3. Reproductibilité:
   • La description algorithmique est détaillée, théoriquement reproductible
   • Mais manque de détails d'implémentation et de code
   • Les preuves détaillées en Appendice aident à la compréhension
4. Recherche ultérieure:
   • Les problèmes de complexité ouverts fournissent une direction claire pour la recherche ultérieure
   • Les fondations techniques peuvent être généralisées à d'autres métriques et applications
   • Peut inspirer de nouvelles idées de conception algorithmique

Scénarios Applicables

1. Recherche théorique:
   • Étude de la complexité computationnelle des métriques de similarité de courbes
   • Conception algorithmique pour les problèmes d'optimisation géométrique
   • Application de nombres transcendantaux en géométrie computationnelle
2. Applications pratiques (potentielles):
   • Analyse de similarité de trajectoires (quand les différences de taux d'échantillonnage sont grandes)
   • Vérification de signatures (nécessitant robustesse aux valeurs aberrantes)
   • Appariement cartographique (appariement de trajectoires GPS)
   • Clustering de séries temporelles
3. Scénarios non applicables:
   • Applications nécessitant un calcul en temps réel (complexité relativement élevée)
   • Données de haute dimension (actuellement limitées à 2D)
   • Applications où la précision n'est pas critique (DTW peut suffire)

Références

Citations Clés

1. Alt & Godau 1995: Algorithme classique de distance de Fréchet
2. Vintsyuk 1968: Définition originale de DTW
3. Baker 1990: Fondations de la théorie des nombres transcendantaux (source du Lemme 10)
4. Buchin 2007: Source de la définition de CDTW
5. Buchin, Nusser & Wong 2022: Algorithme exact de CDTW pour 1D
6. Maheshwari, Sack & Scheffer 2018: Algorithme d'approximation de CDTW pour 2D
7. Brankovic 2022: Algorithme pour norme 1 en 2D

Fondations Théoriques

8. Boyd & Vandenberghe 2009: Optimisation convexe (fonctions de jauge)
9. Schaefer & Wolff 1999: Espaces vectoriels topologiques (théorie des normes)
10. De Carufel et al. 2014: Incalculabilité de la similarité partielle de Fréchet

Évaluation globale: Ceci est un article de géométrie computationnelle théorique de haute qualité, apportant des contributions importantes à la complexité computationnelle et à la conception algorithmique de la CDTW. Le résultat de transcendance est une avancée révolutionnaire dans ce domaine, et le cadre technique possède une bonne généralité. Les principales insuffisances sont l'absence d'évaluation expérimentale et l'analyse de complexité incomplète. L'article convient à la publication dans des conférences de premier plan en géométrie computationnelle (telles que WALCOM, SoCG) et a une valeur de référence importante pour les chercheurs théoriques et ceux intéressés par les métriques de similarité de courbes.