التثليث المضلعي

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

العدد الإجمالي لطرق تقسيم مضلع محدب ذي n ضلعًا إلى مثلثات باستخدام أقطار غير متقاطعة هو عدد كاتالان ( n -2) ، والذي يساوي

${\displaystyle {\frac {n(n+1)...(2n-4)}{(n-2)!}}}$،

صيغة اكتشفها ليونارد أويلر . ^{[ 2 ]}

تعتمد إحدى طرق تقسيم المضلع البسيط إلى مثلثات على نظرية الأذنين ، حيث أن أي مضلع بسيط يحتوي على 4 رؤوس على الأقل بدون ثقوب، يحتوي على أذنين على الأقل ، وهما مثلثان ضلعان منهما يمثلان حواف المضلع، بينما يقع الضلع الثالث داخله تمامًا. ^{[ 3 ]} وتتلخص الخوارزمية في إيجاد إحدى هاتين الأذنين، ثم إزالتها من المضلع (مما ينتج عنه مضلع جديد يستوفي الشروط نفسها)، وتكرار هذه العملية حتى يتبقى مثلث واحد فقط.

هذه الخوارزمية سهلة التطبيق، لكنها أبطأ من بعض الخوارزميات الأخرى، وهي تعمل فقط على المضلعات الخالية من الثقوب. أما التطبيق الذي يحتفظ بقوائم منفصلة للرؤوس المحدبة والمقعرة، فيعمل في زمن O( n² ⁾ . تُعرف هذه الطريقة باسم "قص الأذن" أو "تشذيب الأذن" . وقد اكتشف حسام الجندي، وهازل إيفريت، وغودفريد توسان خوارزمية فعالة لقص الأذن . ^{[ 4 ]}

يكون المضلع البسيط رتيبًا بالنسبة للخط L إذا تقاطع أي خط عمودي على L مع المضلع مرتين على الأكثر. يمكن تقسيم المضلع الرتيب إلى سلسلتين رتيبتين . يُسمى المضلع الرتيب بالنسبة للمحور y مضلعًا رتيبًا بالنسبة للمحور y . يمكن تثليث مضلع رتيب ذي n رأسًا في زمن O( n ) . بافتراض أن المضلع المعطى رتيب بالنسبة للمحور y، تبدأ الخوارزمية الجشعة بالتحرك على إحدى سلسلتي المضلع من الأعلى إلى الأسفل مع إضافة الأقطار كلما أمكن ذلك. ^{[ 1 ]} من السهل ملاحظة إمكانية تطبيق هذه الخوارزمية على أي مضلع رتيب.

يمكن تثليث المضلع الرتيب في وقت خطي باستخدام خوارزمية A. Fournier و DY Montuno، ^{[ 5 ]} أو خوارزمية Godfried Toussaint . ^{[ 6 ]}

إذا لم يكن المضلع رتيبًا، فيمكن تقسيمه إلى مضلعات فرعية رتيبة في زمن قدره O( n log n ) باستخدام أسلوب المسح الخطي . لا تتطلب الخوارزمية أن يكون المضلع بسيطًا، وبالتالي يمكن تطبيقها على المضلعات التي تحتوي على ثقوب . عمومًا، تستطيع هذه الخوارزمية تثليث تقسيم مستوٍ ذي n رأسًا في زمن قدره O( n log n ) باستخدام مساحة قدرها O( n ) . ^{[ 1 ]}

يُعدّ الرسم البياني الثنائي (G( _TP )) رسمًا بيانيًا مفيدًا يرتبط غالبًا بتثليث المضلع P. بفرض تثليث T _P للمضلع P ، يُعرَّف الرسم البياني G ( TP ) بأنه الرسم البياني الذي تتكون رؤوسه من مثلثات T _P ، ويكون رأسان (مثلثان) متجاورين إذا وفقط إذا كانا يشتركان في قطر. من السهل ملاحظة أن G ( TP ) شجرة ذات _درجة قصوى تبلغ 3.

حتى عام 1988، كان تحديد ما إذا كان بالإمكان تثليث مضلع بسيط بسرعة تتجاوز O( n log n ) مسألة مفتوحة في الهندسة الحسابية. ^{[ 1 ]} ثم اكتشف تارجان وفان ويك (1988) خوارزمية للتثليث بزمن O( n log log n ) ، ^{[ 7 ]} والتي بسّطها لاحقًا كيركباتريك وكلاوي وتارجان (1992) . ^{[ 8 ]} وتلتها عدة طرق محسّنة ذات تعقيد زمني O( n log ^* n ) (وهو عمليًا لا يمكن تمييزه عن الزمن الخطي ). ^{[ 9 ] [ 10 ] [ 11 ]}

أظهر برنارد شازيل في عام 1991 أنه يمكن تثليث أي مضلع بسيط في زمن خطي، على الرغم من أن الخوارزمية المقترحة معقدة للغاية. ^{[ 12 ]} كما توجد خوارزمية عشوائية أبسط ذات زمن متوقع خطي. ^{[ 13 ]}

تمت مناقشة خوارزمية التفكيك لسيدل ^{[ 10 ]} وطريقة التثليث لشازيل بالتفصيل في لي وكليت (2011) . ^{[ 14 ]}

يبلغ الحد الأدنى للتعقيد الزمني لتثليث مضلع ذي n رأسًا مع وجود ثقوب Ω( n log n ) في نماذج الحساب الشجري الجبرية. ^{[ 1 ]} من الممكن حساب عدد التثليثات المختلفة لمضلع بسيط في وقت متعدد الحدود باستخدام البرمجة الديناميكية ، وبناءً على خوارزمية العد هذه، يمكن توليد تثليثات عشوائية منتظمة في وقت متعدد الحدود. ^{[ 15 ]} مع ذلك، فإن حساب تثليثات مضلع ذي ثقوب مسألة كاملة من فئة #P ، مما يجعل من غير المرجح إمكانية إنجازها في وقت متعدد الحدود. ^{[ 16 ]}