أساسيات حساب الالتواء الديناميكي المستمر للوقت في بعدين تحت معايير مختلفة

المعلومات الأساسية

• معرّف الورقة: 2511.20420
• العنوان: Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms
• المؤلفون: Kevin Buchin (جامعة دورتموند التقنية)، Maike Buchin (جامعة روهر بوخوم)، Jan Erik Swiadek (جامعة روهر بوخوم)، Sampson Wong (جامعة كوبنهاغن)
• التصنيف: cs.CG (الهندسة الحسابية)
• تاريخ النشر/المؤتمر: WALCOM 2026 (نسخة ما قبل الطباعة، مُقدّمة في نوفمبر 2025)
• رابط الورقة: https://arxiv.org/abs/2511.20420

الملخص

يوفر الالتواء الديناميكي المستمر للوقت (CDTW) قياساً قوياً لتشابه المنحنيات المضلعة، مع متانة تجاه القيم الشاذة ومعدلات الأخذ. ومع ذلك، يواجه تصميم وتحليل خوارزميات CDTW تحديات متعددة. تثبت هذه الورقة أنه تحت معيار 2-الإقليدسي، لا يمكن حساب CDTW بدقة باستخدام العمليات الجبرية وحدها، وتقدم خوارزمية دقيقة لحساب CDTW تحت معايير تقريب معيار 2. يعتمد الأخير على أساس تقني أنشأه المؤلفون، والذي يمكن تعميمه على معايير عشوائية والمقاييس ذات الصلة (مثل تشابه Fréchet الجزئي).

الخلفية البحثية والدافع

مشكلة البحث

تبحث هذه الورقة عن كيفية حساب مسافة الالتواء الديناميكي المستمر للوقت (CDTW) بين منحنيات مضلعة في الفضاء ثنائي الأبعاد بكفاءة ودقة.

أهمية المشكلة

1. التطبيقات العملية الواسعة: يتمتع CDTW بتطبيقات مهمة في التحقق من التوقيعات، ومطابقة الخرائط، وتجميع المسارات
2. التغلب على قيود الطرق المنفصلة: يتجاهل DTW التقليدي الاستمرارية في المنحنيات، مما ينتج عنه نتائج سيئة عندما تكون معدلات الأخذ مختلفة أو غير كافية
3. متطلبات المتانة: بالمقارنة مع مقياس القيمة القصوى لمسافة Fréchet الحساسة للقيم الشاذة، يستخدم CDTW تكاملاً للمسار، مما يوفر معالجة أفضل للقيم الشاذة

قيود الطرق الموجودة

1. الطرق التقريبية والاستكشافية: تتعامل العديد من الطرق الموجودة مع التكامل من خلال تقسيم منحنيات الإدخال، مما يؤدي إلى جودة الحل أو وقت التشغيل يعتمد على دقة التقسيم
2. قيود البعد: كانت الخوارزميات الدقيقة السابقة محصورة بشكل أساسي في الحالة أحادية البعد، أو فقط خوارزميات تقريب (1+ε) بوقت شبه متعدد الحدود تحت معيار 2-الإقليدسي في بعدين
3. فهم نظري غير كافٍ: لم يتم فهم الخصائص الأساسية لـ CDTW، خاصة تحت معايير مختلفة في بعدين، بشكل كافٍ

الدافع البحثي

يهدف المؤلفون إلى:

1. فهم عميق لتعقيد حساب CDTW، خاصة عدم القابلية للحساب تحت معيار 2
2. إنشاء أساس تقني ينطبق على معايير عشوائية
3. تصميم خوارزميات دقيقة/تقريبية تتجنب تقسيم المنحنيات

المساهمات الأساسية

1. نظرية الأمثلية المحلية (القسم 2): تثبت أن تعريف CDTW القائم على تكامل المسار يسمح بمطابقة محلية مثلى مفيدة من وجهة نظر خوارزمية، وتؤسس وجود وطريقة حساب الوديان (valleys)، ينطبق على أي معيار
2. نتائج عدم القابلية للحساب (القسم 3): تثبت أنه تحت معيار 2-الإقليدسي، قد تكون الأرقام المتضمنة في CDTW أرقاماً متسامية (transcendental numbers)، وبالتالي لا يمكن حسابها بدقة باستخدام العمليات الجبرية وحدها (نموذج ACMQ)
3. خوارزمية المعايير المضلعة (القسم 4): تقترح خوارزمية دقيقة لحساب CDTW تحت معايير ذات مجموعات مستويات مضلعة، التي:
   • لا تتطلب تقسيم منحنيات الإدخال
   • يمكن استخدامها للحصول على تقريب (1+ε) تحت معيار 2
   • تستخدم معايير مضلعة منتظمة مع k ∈ O(ε^(-1/2))
4. الخصائص التقنية: تؤسس عدة خصائص تقنية بما فيها استمرارية الدالة المثلى وترتيب الانتشار، مما يضع الأساس لتحليل التعقيد

شرح الطريقة

تعريف المهمة

الإدخال:

• منحنيان مضلعان ثنائي الأبعاد P = ⟨p₀, ..., pₙ⟩ و Q = ⟨q₀, ..., qₘ⟩
• معيار ‖·‖

الإخراج:

• قيمة CDTW: cdtw‖·‖(P,Q)

تعريف CDTW (التعريف 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$

حيث:

• Π(P) يحتوي على جميع المعاملات الرتيبة والقابلة للتفاضل بشكل متقطع لـ P
• d(·,·) هي دالة المسافة (تستخدم هذه الورقة d(p,q) = ‖p-q‖)
• يتم استخدام معيار 1 لتطبيع السرعة، مما يجعل طول قوس المسار σ = ‖P‖ + ‖Q‖

الإطار التقني الأساسي

1. فضاء المعاملات والمسارات المثلى (القسم 2)

فضاء المعاملات (التعريف 2): 0, ‖P‖ × 0, ‖Q‖، مقسم إلى خلايا n×m

مفهوم الوادي (Valley) (التعريف 4):

• الوادي ℓ هو خط مستقيم في فضاء المعاملات (الميل ≠ -1)
• كل نقطة z ∈ ℓ هي sink (نقطة تصريف): تصل الدالة على طول خط بميل -1 إلى الحد الأدنى عند z

النظرية الرئيسية (النظرية 8): بالنسبة لأي معيار ‖·‖ وأجزاء مضلعة P, Q، يوجد وادٍ بميل موجب. يتم إثبات هذا من خلال الثنائية والتحليل الهندسي:

• استخدام Lemma 7 لتقليل دالة gauge على الخط
• إثبات وجود نقطة تعظيم بمكونات موجبة v*
• بالنسبة للمعايير المضلعة، يمكن حساب الوادي في وقت O(1) (Corollary 9)

خصائص المسار الأمثل (النظرية 5): بالنظر إلى الوادي ℓ، يتتبع المسار الأمثل (x,y) بالطريقة التالية:

• إذا تقاطع ℓ مع المستطيل Ξ = x₁,y₁×x₂,y₂، يتتبع المسار من x إلى x̂ (على ℓ) إلى ŷ (على ℓ) إلى y
• وإلا، يتتبع المسار من x إلى ξ إلى y، حيث ξ هي النقطة الأقرب إلى ℓ في Ξ

2. نتيجة التسامي (القسم 3)

النظرية الرئيسية (النظرية 11): تبني منحنيات بها رؤوس صحيحة P, Q بحيث:

• (أ) cdtw‖·‖₂(P,Q) هو رقم متسامٍ
• (ب) إحداثيات نقاط الانعطاف لكل مسار أمثل هي أرقام متسامية

فكرة الإثبات:

• بناء منحنيات محددة: جزأان لـ P وثلاثة أجزاء لـ Q
• من خلال حساب التكامل، الحصول على قيمة CDTW تحتوي على حدود لوغاريتمية
• استخدام نظرية Baker (نتيجة من نظرية الأرقام المتسامية، Lemma 10) لإثبات أن الأرقام المتضمنة ليست جبرية
• بالنسبة لـ (ب)، إثبات أن النقطة التي تقلل المشتقة هي أيضاً رقم متسامٍ

الأهمية: يشير هذا إلى أنه تحت معيار 2، لا يقتصر CDTW على عدم التعبير عنه بالجذور، بل هو ليس حتى رقماً جبرياً، وبالتالي لا يمكن لأي خوارزمية دقيقة تستخدم العمليات الجبرية أن توجد.

3. خوارزمية المعايير المضلعة (القسم 4)

إطار الخوارزمية: البرمجة الديناميكية، من خلال نشر تكلفة المسار الأمثل عبر خلايا فضاء المعاملات

إعداد المعيار:

• استخدام معايير Gψ(Rₖ) مع مجموعات 1-sublevel ψ(Rₖ)
• Rₖ هو k-gon منتظم (k زوجي)، مع رؤوس vᵣ = (cos(θᵣ), sin(θᵣ))ᵀ، θᵣ = r·2π/k
• ψ: ℝ² → ℝ² هي خريطة خطية ثنائية الاتجاه

الخصائص الرئيسية (Lemma 14):

• (أ) يمكن تقييم Gψ(Rₖ) في وقت O(1)، خطي على كل مخروط
• (ب) يمكن تمثيل فضاء الانتشار ΣA,B باستخدام ترتيب O(k) من الخطوط، optA,B تربيعي على كل وجه
• (ج) دالة الأمثلية opt₀,B مقسمة تربيعية

عملية الانتشار (الخوارزمية Propagate):

الإدخال: أجزاء المنحنى P,Q، الحد B، دوال الأمثلية للحدود المجاورة والمقابلة
الإخراج: دالة الأمثلية لـ B (مقسمة تربيعية)

1. حساب الوادي ℓ (وقت O(1)، Corollary 9)
2. لكل حد A ∈ {adj(B), opp(B)}:
   - بناء ترتيب O(k) من الخطوط
   - دمج مع نقاط الانقطاع في opt₀,A
   - معالجة الفترات بترتيب مناسب (Lemma 15)
   - لكل فترة I:
     * جمع دوال المرشحين على الحواف والوجوه
     * حساب الغلاف السفلي (وقت O(Xᵢlog(Xᵢ)α(Xᵢ)))
     * تحديث النتيجة باستخدام المكدس
3. إرجاع دالة الأمثلية المقسمة التربيعية

ترتيب الانتشار (Lemma 15): تحديد ترتيب الانتشار الصحيح من خلال إثبات عدم تقاطع اللواحق من المسارات المقابلة:

• إذا كان A و B في نفس الاتجاه (مثل A = opp(B))، فإن s < s'
• إذا كان A و B متعامدين (مثل A = adj(B))، فإن s > s'

ضمان التقريب (Corollary 17):

• يمكن حساب CDTW بدقة باستخدام معايير k-gon منتظمة Gψ(Rₖ)
• الحصول على تقريب (1+ε) تحت معيار 2 من خلال k ∈ O(ε^(-1/2))
• الإثبات: 1/cos(π/k)² ≤ 1+ε

نقاط الابتكار التقني

1. طريقة الثنائية الهندسية: استخدام خصائص الثنائية لدوال gauge والهندسة المحدبة لإثبات وجود الوديان وخاصية الميل الموجب
2. تطبيق نظرية الأرقام المتسامية: أول تطبيق لنظرية Baker على CDTW، مما يثبت نتيجة أقوى من "لا يمكن التعبير عنها بالجذور"
3. تجنب التقسيم: من خلال الاستفادة من الخطية المقسمة للمعايير المضلعة، العمل مباشرة على المنحنيات المستمرة بدلاً من التقسيم
4. البرمجة الديناميكية المستندة إلى المكدس: الاستفادة من خصائص ترتيب الانتشار (Lemma 15)، استخدام بنية بيانات المكدس لتسريع حساب الغلاف السفلي
5. إطار موحد: يسمح الأساس التقني المؤسس بالتعميم على معايير عشوائية وقياسات ذات صلة (مثل تشابه Fréchet الجزئي)

إعداد التجربة

ملاحظة: هذه ورقة نظرية، والمساهمات الرئيسية هي الخوارزميات وتحليل التعقيد، وليس تجارب بالمعنى التقليدي. يركز الورقة على:

• الإثباتات النظرية
• صحة الخوارزمية
• تحليل التعقيد

التحقق النظري

1. التحقق من التسامي (القسم 3):
   • بناء أمثلة محددة للتحقق من النظرية 11
   • المثال (أ): P = ⟨(1,2)ᵀ, (1,-4)ᵀ⟩, Q = ⟨(0,0)ᵀ, (5,0)ᵀ⟩
   • الحساب يعطي: cdtw = ½·ln(α₁) - 1/√2 - ½·ln(α₂) + √5 + 17√2
   • حيث α₁ = √2-1, α₂ = √5-2
   • إثبات أن هذا رقم متسامٍ من خلال Lemma 10
2. صحة الخوارزمية:
   • النظرية 16 تثبت صحة خوارزمية Propagate
   • النظرية 20 تثبت استمرارية دالة الأمثلية
   • Lemma 19 تثبت تقارب سلسلة المسارات

تحليل التعقيد

وقت التشغيل (Proposition 18):

• الوقت الإجمالي: O(N·k²log(k)α(k))
• N: العدد الإجمالي للأجزاء التربيعية في جميع دوال الأمثلية
• α: دالة Ackermann العكسية

المشاكل غير المحلولة:

• في الحالة أحادية البعد، ثبت أن N ∈ O(n⁵)
• في الحالة ثنائية الأبعاد، لم يتم بعد إنشاء حد متعدد الحدود لـ N
• الصعوبة الرئيسية: قد تؤدي الخطوط ذات الميل السالب في الترتيب إلى سلوك مضاعفة (الشكل 5)

نتائج التجربة

ملخص النتائج النظرية

1. عدم القابلية للحساب:
   • إثبات واضح أن CDTW تحت معيار 2 ينطوي على أرقام متسامية
   • استبعاد إمكانية الخوارزميات الجبرية البحتة
   • توفير دعم نظري للخوارزميات التقريبية
2. فعالية الخوارزمية:
   • يمكن الحساب الدقيق تحت المعايير المضلعة
   • الحصول على تقريب (1+ε) لمعيار 2، مع k = O(ε^(-1/2))
   • لا يتطلب تقسيم منحنيات الإدخال
3. الشمولية:
   • وجود الوادي ينطبق على جميع المعايير
   • يمكن تعميم الإطار التقني على مقاييس أخرى

تحليل الحالات

المثال 1 (الشكل 4، النظرية 11أ):

• منحنيات بسيطة: جزآن وجزء واحد
• خلية فضاء معاملات واحدة
• المسار الأمثل له 3 أجزاء: جزآن على الوادي، جزء واحد أفقي
• قيمة CDTW تحتوي على حد لوغاريتمي، مثبت أنه رقم متسامٍ

المثال 2 (الشكل 4، النظرية 11ب):

• منحنيات: ثلاثة أجزاء وجزء واحد
• خليتا فضاء معاملات
• المسار الأمثل المرشح γₛ معامل كـ s ∈ 0,10
• من خلال تحليل حلول C'(s) = 0، إثبات أن نقطة التقليل s* هي رقم متسامٍ
• التحقق الرقمي: s* ≈ 2.08، بينما المرشح الجبري الوحيد s₀* ≈ 4.31

الأعمال ذات الصلة

DTW ومسافة Fréchet

• DTW القياسي: وقت O(n²) Vintsyuk 1968
• مسافة Fréchet: وقت O(n²log n) Alt & Godau 1995
• حدود محسّنة: توجد حدود أفضل Gold & Sharir 2018; Buchin et al. 2017; Cheng & Huang 2025

متغيرات DTW المستمرة

• Serra & Berthod 1994: النسخة المستمرة الأولى، مطابقة مستمرة لكن مجموع محدود
• Munich & Perona 1999: تعريف معادل وتحليل
• Serra & Berthod 1995: نسخة ثابتة الإزاحة بناءً على تغيير متجهات المسافة
• Efrat et al. 2007: نسخة متكاملة أكثر عمومية
• Buchin 2007: التعريف المستخدم في هذه الورقة

خوارزميات دقيقة وتقريبية

• Klaren 2020, Buchin et al. 2022: خوارزمية دقيقة بوقت متعدد الحدود في الحالة أحادية البعد
• Maheshwari et al. 2018: تقريب بوقت شبه متعدد الحدود (1+ε) تحت معيار 2-الإقليدسي في بعدين
• Brankovic 2022: خوارزمية تحت معيار 1 في بعدين

نتائج عدم القابلية للحساب

• De Carufel et al. 2014: لا يمكن حساب تشابه Fréchet الجزئي باستخدام الجذور
• Bajaj 1988, De Carufel et al. 2014: الدرجة الجبرية لمشاكل التحسين الهندسي ذات الصلة
• هذه الورقة: نتيجة تسامي أقوى

مقاييس ذات صلة

• مسافة Fréchet بالترتيب المعجمي Rote 2014
• تشابه Fréchet الجزئي Buchin et al. 2009
• تشترك هذه المقاييس مع CDTW في خصائص الأمثلية المحلية

الخلاصة والمناقشة

الاستنتاجات الرئيسية

1. المساهمات النظرية:
   • تحت معيار 2، يتطلب الحساب الدقيق لـ CDTW أرقاماً متسامية، خارج نموذج الحساب الجبري
   • توجد وديان بميل موجب تحت أي معيار، مما يضمن جدوى تصميم الخوارزمية
   • تأسيس أساس تقني ينطبق على أي معيار
2. المساهمات الخوارزمية:
   • توفير خوارزمية دقيقة تحت المعايير المضلعة
   • الحصول على تقريب (1+ε) لمعيار 2 من خلال k-gons منتظمة مع k = O(ε^(-1/2))
   • تجنب تقسيم منحنيات الإدخال
3. المشاكل المفتوحة:
   • لم يتم بعد إنشاء حد متعدد الحدود في الحالة ثنائية الأبعاد
   • التحدي الرئيسي هو سلوك المضاعفة المحتمل الناجم عن الخطوط ذات الميل السالب في الترتيب

القيود

1. تحليل التعقيد غير المكتمل:
   • بينما يتم إعطاء حد O(N·k²log(k)α(k))، لم يتم إنشاء حد متعدد الحدود لـ N
   • لا يمكن تعميم تقنية تحليل O(n⁵) في الحالة أحادية البعد مباشرة على بعدين
2. عدم التحقق من الكفاءة العملية:
   • الورقة نظرية بحتة، بدون تنفيذ وتقييم تجريبي
   • قد يتأثر وقت التشغيل الفعلي بشكل كبير بـ k و N
3. اعتماد عامل التقريب:
   • k = O(ε^(-1/2)) يعني أن ε الصغيرة تتطلب k كبيرة
   • على سبيل المثال، ε = 0.01 يتطلب k ≈ 314
4. الاستقرار الرقمي:
   • بينما يتم تجنب الحساب الدقيق للأرقام المتسامية، لا تزال مشاكل الأخطاء المتراكمة موجودة (مذكورة في القسم 3)

الاتجاهات المستقبلية

1. تحليل التعقيد:
   • حل مشكلة حد متعدد الحدود لـ N في الحالة ثنائية الأبعاد
   • معالجة سلوك المضاعفة بشكل خاص في الشكل 5
2. التنفيذ العملي:
   • تنفيذ الخوارزمية وإجراء تقييم تجريبي
   • مقارنة مع الطرق القائمة على التقسيم الموجودة
3. التطبيقات الموسعة:
   • تعميم التقنيات على مقاييس ذات صلة مثل تشابه Fréchet الجزئي
   • استكشاف مجالات تطبيق أخرى
4. تحسين التقريب:
   • البحث عما إذا كان يمكن الحصول على نفس ضمان التقريب باستخدام k أصغر
   • استكشاف استراتيجيات تقريب بديلة

التقييم المتعمق

المميزات

1. العمق النظري:
   • نتيجة التسامي هي مساهمة نظرية مهمة في هذا المجال، أقوى من "لا يمكن التعبير عنها بالجذور"
   • تقنية الإثبات باستخدام نظرية Baker مبتكرة وصارمة
   • الإثبات الهندسي لوجود الوديان أنيق وعام
2. الصرامة التقنية:
   • جميع النظريات لها إثباتات كاملة (في النص الرئيسي أو الملحق)
   • الاشتقاقات الرياضية مفصلة، خاصة الإثبات المفصل للتسامي في الملحق B
   • تم النظر في حالات حدية متعددة
3. الشمولية:
   • الإطار المؤسس ينطبق على أي معيار
   • يمكن تعميمه على مقاييس ذات صلة (مسافة Fréchet بالترتيب المعجمي، تشابه Fréchet الجزئي)
   • النظريات مثل النظرية 8 و Lemma 15 لها قيمة مستقلة
4. تصميم الخوارزمية:
   • تجنب التقسيم هو مساهمة منهجية مهمة
   • استخدام البنية الهندسية للمشكلة في الانتشار المستند إلى المكدس
   • تصميم خوارزمية Propagate واضح وسهل الفهم
5. جودة الكتابة:
   • البنية واضحة، تتقدم من الدافع إلى النظرية إلى الخوارزمية بشكل متدرج
   • الأشكال (الأشكال 1-9) تساعد على الفهم
   • مراجعة الأعمال ذات الصلة شاملة

أوجه القصور

1. غياب التجارب:
   • كورقة خوارزمية، تفتقد إلى التنفيذ الفعلي والتقييم التجريبي
   • لا يمكن تقييم الكفاءة الفعلية وقابلية الاستخدام للخوارزمية
   • غياب المقارنة بالأداء الفعلي مع الطرق الموجودة
2. عدم اكتمال تحليل التعقيد:
   • حد متعدد الحدود لـ N هو مشكلة مفتوحة رئيسية
   • لم يتم إعطاء اتجاه واضح لحل سلوك المضاعفة
   • هذا يحد من الاكتمال النظري للخوارزمية
3. معاملات التقريب:
   • الاعتماد k = O(ε^(-1/2)) ضعيف نسبياً
   • ε الصغيرة تتطلب k كبيرة، قد تؤثر على الكفاءة العملية
   • لا توجد مناقشة لتأثير قيم k الفعلية على الأداء
4. المشاكل الرقمية:
   • بينما يتم تجنب حساب الأرقام المتسامية، لم تتم مناقشة مشكلة الأخطاء المتراكمة المذكورة في القسم 3 بشكل كافٍ
   • لم يتم تحليل الاستقرار الرقمي للدوال التربيعية المقسمة
5. مناقشة التطبيقات:
   • مناقشة سيناريوهات التطبيق العملي محدودة
   • لا توجد مناقشة حول متى يجب استخدام CDTW بدلاً من DTW أو مسافة Fréchet

التأثير

1. التأثير النظري:
   • نتيجة التسامي هي تقدم مهم في تعقيد حساب مقاييس تشابه المنحنيات
   • توفير أساس نظري قوي لضرورة الخوارزميات التقريبية
   • قد يلهم الإطار التقني البحث في مشاكل ذات صلة
2. القيمة العملية:
   • خوارزمية التقريب (1+ε) لها قيمة للتطبيقات العملية
   • قد يحسن تجنب التقسيم جودة الحل
   • لكن الكفاءة الفعلية تتطلب التحقق التجريبي
3. القابلية للتكرار:
   • وصف الخوارزمية مفصل، يمكن تكراره من الناحية النظرية
   • لكن تفاصيل التنفيذ والكود غير متوفرة
   • الإثباتات المفصلة المقدمة في الملحق تساعد على الفهم
4. البحث اللاحق:
   • توفر المشاكل المفتوحة في التعقيد اتجاهات بحثية واضحة
   • يمكن تعميم الأساس التقني على مقاييس أخرى وتطبيقات
   • قد يلهم أفكار تصميم خوارزميات جديدة

السيناريوهات المناسبة

1. البحث النظري:
   • دراسة تعقيد الحساب لمقاييس تشابه المنحنيات
   • تصميم الخوارزميات لمشاكل التحسين الهندسي
   • تطبيق الأرقام المتسامية في الهندسة الحسابية
2. التطبيقات العملية (محتملة):
   • تحليل تشابه المسارات (عندما تكون معدلات الأخذ مختلفة بشكل كبير)
   • التحقق من التوقيعات (يتطلب متانة تجاه القيم الشاذة)
   • مطابقة الخرائط (مطابقة مسارات GPS)
   • تجميع السلاسل الزمنية
3. السيناريوهات غير المناسبة:
   • التطبيقات التي تتطلب حساباً في الوقت الفعلي (التعقيد مرتفع)
   • البيانات عالية الأبعاد (حالياً مقتصرة على بعدين)
   • التطبيقات التي لا تتطلب دقة عالية (قد يكون DTW كافياً)

المراجع

الاستشهادات الرئيسية

1. Alt & Godau 1995: الخوارزمية الكلاسيكية لمسافة Fréchet
2. Vintsyuk 1968: التعريف الأصلي لـ DTW
3. Baker 1990: أساس نظرية الأرقام المتسامية (مصدر Lemma 10)
4. Buchin 2007: مصدر تعريف CDTW
5. Buchin, Nusser & Wong 2022: خوارزمية دقيقة لـ CDTW في الحالة أحادية البعد
6. Maheshwari, Sack & Scheffer 2018: خوارزمية تقريب CDTW في بعدين
7. Brankovic 2022: خوارزمية تحت معيار 1 في بعدين

الأساس النظري

8. Boyd & Vandenberghe 2009: التحسين المحدب (دوال gauge)
9. Schaefer & Wolff 1999: فضاءات المتجهات الطوبولوجية (نظرية المعايير)
10. De Carufel et al. 2014: عدم القابلية للحساب لتشابه Fréchet الجزئي

التقييم الشامل: هذه ورقة عالية الجودة في الهندسة الحسابية النظرية، تقدم مساهمات مهمة في تعقيد الحساب وتصميم الخوارزميات لـ CDTW. نتيجة التسامي هي تقدم حقيقي في هذا المجال، والإطار التقني له شمولية جيدة. أوجه القصور الرئيسية هي غياب التقييم التجريبي وعدم اكتمال تحليل التعقيد. الورقة مناسبة للنشر في مؤتمرات الهندسة الحسابية الرائدة (مثل WALCOM و SoCG)، وذات قيمة مرجعية مهمة للباحثين النظريين والمهتمين بمقاييس تشابه المنحنيات.