The longest-edge bisection algorithm may produce degenerating tetrahedra

ملخص تقني: "خوارزمية تنصيف الحافة الأطول قد تنتج رباعيات أوجه متدهورة"

بيان المشكلة
تتناول الورقة فجوة حرجة في نظرية تنعيم الشبكات رباعية الأوجه (tetrahedral mesh refinement). فبينما تُعد خوارزمية تنصيف الحافة الأطول تقنية قياسية لبناء شبكات بسيطة متداخلة (nested simplicial meshes)، فإن سلوكها في الأبعاد الثلاثية ليس مفهوماً بشكل كامل فيما يتعلق بعدم التدهور. في البعدين، يُعد التقارب وانتظام الشكل للمثلثات الناتجة عن تنصيف الحافة الأطول المتكرر أمراً راسخاً ومثبتاً. ومع ذلك، في الأبعاد الثلاثة، تفتقر التعليمات الهندسية غير المقيدة — حيث يجب تنصيف الحافة الأطول حالياً ولكن يمكن اختيار أي حافة إذا تساوت عدة حواف في الطول — إلى ضمان عدم التدهور. ركزت الدراسات السابقة على مخططات الحواف المحددة (marked-edge schemes) التي تضمن فئات تشابه محدودة، أو عائلات معينة من رباعيات الأوجه، لكن سلوك القاعدة العامة غير المقيدة مع أي اختيار عشوائي عند تساوي الأطوال يظل سؤالاً مفتوحاً.

المنهجية
يبني المؤلف مثالاً مضاداً صريحاً ودقيقاً لإثبات أن القاعدة غير المقيدة يمكن أن تؤدي إلى التدهور. وتتضمن المنهجية ما يلي:

1. تعريف عائلة معلمية (Parametric Family): تم تعريف رباعي أوجه محدد $E(a)$ بقمم تعتمد على معلم $0 < a \le 1$.
2. تكرار ذي خطوتين: تحلل الورقة عملية تنصيف مكونة من خطوتين:
   • الخطوة 1: تنصيف الحافة الوحيدة الأطول $AD$ في $E(a)$ والاحتفاظ برباعي الوجه الناتج (الابن) $O(a)$.
   • الخطوة 2: في $O(a)$، يتساوى طول الحافتين $BD$ و $DC$ تماماً كأطول حواف. يختار المؤلف الحافة $BD$ للتنصيف، ويحتفظ برباعي الوجه الناتج $F(a)$، ويعيد تسمية رؤوسه.
3. إثبات التطابق الدقيق: يتم إثبات أن رباعي الوجه الناتج $F(a)$ يطابق (congruent) عضو العائلة الأصلي $E(a/2)$. وهذا يثبت وجود علاقة تكرارية حيث يتم تنصيف معلم الشكل $a$ عند كل خطوتين من خطوات التنصيف.
4. البناء التكراري: بدءاً من $E(1)$، تولد هذه العملية تسلسلاً لانهائياً من رباعيات الأوجه $E(1) \to O(1) \to E(1/2) \to O(1/2) \to \dots$.
5. تحليل الانتظام: يحسب المؤلف نسبة الحجم المعيرة ($|T|/h_T^3$) وزوايا ثنائية الوجه (dihedral angles) محددة للتسلسل مع اقتراب $a \to 0$ (حيث $a_k = 2^{-k}$) للاختبار مقابل معايير الانتظام القياسية.

المساهمات والنتائج الرئيسية
تقدم الورقة برهاناً صارماً على أن خوارمة تنصيف الحافة الأطول غير المقيدة في الأبعاد الثلاثية يمكن أن تنتج تسلسلاً من رباعيات الأوجه المتدهورة. وتتمثل النتائج المحددة فيما يلي:

• انتهاك انتظام الشكل: نسبة الحجم المعيرة $|E_k|/h_{E_k}^3$ تؤول إلى الصفر عندما $k \to \infty$. وتحديداً، تتناقص النسبة تقاربياً بمعدل $2^{-k/2}$، مما يثبت عدم وجود حد أدنى موجب موحد لهذه العائلة.
• انتهاك شرط الزاوية الدنيا: زاوية ثنائية الوجه الداخلية $\delta(a)$ عند الحافة $CD$ في $E(a)$ تؤول إلى الصفر. توضح الورقة أن $\delta(a) \sim \sqrt{8a/7}$، مما يعني أن التسلسل يحتوي على زوايا "مسطحة" بشكل تعسفي.
• انتهاك شرط الزاوية القصوى: الزاوية ثنائية الوجه الداخلية $\Theta(a)$ عند الحافة $MC$ في $O(a)$ تؤول إلى $\pi$. يقترب جيب تمام هذه الزاوية من $-1$، مما يشير إلى أن رباعيات الأوجه تصبح "شبه مسطحة" (sliver-like) أو مسطحة في تكوين مختلف.
• دور كسر التعادل (Tie-Breaking): ينجم التدهور عن تكرار التعادل في أطوال الحواف الأطول ($BD = DC$). وتوضح الورقة أن قاعدة حاسمة بسيطة لكسر التعادل (اختيار الحافة المقابلة للحافة الأطول) كافية لاختيار هذا المسار "السيئ".

الأهمية والادعاءات
ادعاء الورقة الأساسي متواضع ولكنه حاسم: فهي تثبت وجود مدار مقبول متدهور تحت قاعدة الحافة الأطول غير المقيدة. إن استخدام كلمة "قد" في العنوان أمر جوهري؛ فالبناء لا يزعم أن كل اتفاقية لكسر التعادل ستؤدي إلى التدهور، ولا يدعي أن جميع المدارات متدهورة. بل يثبت أنه بدون آليات صريحة لحل مشكلة تساوي الأطوال (tie-resolution mechanisms) مدرجة ضمن الخوارزمية ومحللة كجزء من نظرية الانتظام، فإن الخوارزمية ليست مضمونة لإنتاج شبكات غير متدهورة.

يعمل هذا العمل كنموذج مضاد للافتراض القائل بأن قاعدة الاختيار الهندسي وحدها كافية للانتظام في الأبعاد الثلاثة. وهو يسلط الضل على أن سلوك التنعيم في الأبعاد الثلاثة يعتمد بشكل حاسم على اصطلاحات تحديد الحواف (marking) وكسر التعادل، وأن الاختيارات التعسفية بين الحواف المتساوية في الطول يمكن أن تؤدي إلى فقدان انتظام الشكل، وحدود الزاوية الدنيا، وحدود الزاوية القصوى في آن واحد.