المثلث الزائف

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

على الرغم من استخدام مصطلحي "المثلث الزائف" و"التثليث الزائف" بمعانٍ مختلفة في الرياضيات منذ زمن طويل، ^{[ 1 ]} فقد طُرحت المصطلحات المستخدمة هنا لأول مرة عام 1993 من قِبل ميشيل بوتشيولا وجيرت فيجتر في سياق حساب علاقات الرؤية والمماسات الثنائية بين العوائق المحدبة في المستوى. وقد تناولت إيليانا سترينو (2000، 2005) التثليثات الزائفة المدببة لأول مرة كجزء من حلها لمسألة مسطرة النجار ، وهو برهان على إمكانية تقويم أي مسار مضلع بسيط في المستوى من خلال سلسلة من الحركات المتصلة. كما استُخدمت التثليثات الزائفة في الكشف عن التصادم بين الأجسام المتحركة ^{[ 2 ]} وفي رسم الرسوم البيانية الديناميكية وتغيير الأشكال. ^{[ 3 ]} تظهر التثليثات الزائفة المدببة في نظرية الصلابة كأمثلة على الرسوم البيانية المستوية ذات الصلابة الدنيا ، ^{[ 4 ]} وفي طرق وضع الحراس فيما يتعلق بنظرية معرض الفنون . ^{[ 5 ]} يؤدي تغليف مجموعة نقاط مستوية مضادة إلى ظهور التثليثات الزائفة المدببة، [ ^{6 ] على} الرغم من أنه لا يمكن أن تنشأ جميع التثليثات الزائفة المدببة بهذه الطريقة.

للاطلاع على دراسة تفصيلية لجزء كبير من المواد التي تمت مناقشتها هنا، انظر Rote و Santos و Streinu (2008).

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

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

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

التثليث الزائف هو تقسيم منطقة من المستوى إلى مثلثات زائفة. أي تثليث لمنطقة من المستوى هو تثليث زائف. بينما يجب أن يكون لأي تثليثين لنفس المنطقة نفس عدد الأضلاع والمثلثات، فإن الأمر ليس كذلك بالنسبة للتثليثات الزائفة؛ على سبيل المثال، إذا كانت المنطقة نفسها مثلثًا زائفًا متعدد الأضلاع ذو n رأسًا، فقد يحتوي التثليث الزائف لها على مثلث زائف واحد و n ضلعًا، أو على n − 2 مثلثًا زائفًا و 2 n − 3 ضلعًا.

التثليث الزائف الأدنى هو تثليث زائف T بحيث لا يوجد رسم بياني جزئي من T يمثل تثليثًا زائفًا يغطي نفس المنطقة المحدبة من المستوى. يجب أن يحتوي التثليث الزائف الأدنى ذو n رأسًا على 2n - 3 حواف على الأقل ؛ إذا كان يحتوي على 2n - 3 حواف بالضبط ، فلا بد أن يكون تثليثًا زائفًا مدببًا، ولكن توجد تثليثات زائفة دنيا ذات 3n - O(1) حافة. ^{​​[ 8 ]}

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

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

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

يجب أن يحتوي التثليث الزائف ذو الرؤوس v على 2v - 3 أضلاع بالضبط . ^{[ 9 ]} ويستنتج هذا من خلال حجة بسيطة تعتمد على خاصية أويلر : بما أن كل وجه، باستثناء الوجه الخارجي، هو مثلث زائف بثلاث زوايا محدبة، فإن التثليث الزائف يجب أن يحتوي على 3f - 3 زوايا محدبة بين الأضلاع المتجاورة. كل ضلع هو الضلع الذي يدور باتجاه عقارب الساعة لزاويتين، لذا يوجد إجمالي 2e زاوية ، جميعها محدبة باستثناء v . وبالتالي، 3f - 3 = 2e - v . بدمج هذا مع معادلة أويلر f − e + v = 2 وحل المعادلات الخطية المتزامنة الناتجة، نحصل على e = 2 v − 3. وتُظهر الحجة نفسها أيضًا أن f = v − 1 (بما في ذلك الغلاف المحدب كأحد الأوجه)، لذا يجب أن يحتوي التثليث الزائف على v − 2 مثلثًا زائفًا بالضبط.

وبالمثل، بما أن أي رسم بياني فرعي ذي k رأس من تثليث زائف مدبب يمكن إكماله لتشكيل تثليث زائف مدبب لرؤوسه، فلا بد أن يحتوي الرسم البياني الفرعي على 2k - 3 حواف على الأكثر. وبالتالي، فإن التثليثات الزائفة المدببة تحقق الشروط التي تحدد رسوم لامان البيانية : فهي تحتوي على 2v - 3 حواف بالضبط ، ورسومها البيانية الفرعية ذات k رأس تحتوي على 2k - 3 حواف على الأكثر . تُعد رسوم لامان البيانية، وبالتالي التثليثات الزائفة المدببة، رسومًا بيانية صلبة بشكل طفيف في بعدين. يمكن رسم أي رسم لامان بياني مستوٍ على شكل تثليث زائف مدبب، مع العلم أن ليس كل رسم مستوٍ لرسم لامان بياني مستوٍ هو تثليث زائف. ^{[ 10 ]}

هناك طريقة أخرى لإيجاد مثلث زائف مُدبَّب، وهي تقشير مجموعة النقاط؛ أي إزالة رؤوس الغلاف المحدب واحدة تلو الأخرى حتى إزالة جميع النقاط. تُشكِّل عائلة تسلسلات الإزالة التي يُمكن تكوينها بهذه الطريقة المصفوفة المضادة للتقشير لمجموعة النقاط، وتُشكِّل مجموعة حواف الأغلفة المحدبة لتسلسل مجموعات النقاط المُشكَّلة بعملية الإزالة هذه مثلثًا زائفًا. ^{[ 6 ]} مع ذلك، لا يُمكن تكوين جميع المثلثات الزائفة المُدبَّبة بهذه الطريقة.

أظهر آيتشولزر وآخرون (2004) أن مجموعة من n نقطة، h منها تنتمي إلى الغلاف المحدب للمجموعة، يجب أن تحتوي على الأقل على C _{_{h -2}} × 3 ^{^{n - h}} من التثليثات الزائفة ذات النقاط المختلفة، حيث C _{_i} هو العدد الكاتالاني رقم i . ونتيجة لذلك، أظهروا أن مجموعات النقاط التي تحتوي على أقل عدد من التثليثات الزائفة ذات النقاط هي مجموعات رؤوس المضلعات المحدبة. وقد بحث آيتشولزر وآخرون (2006) مجموعات النقاط التي تحتوي على أعداد كبيرة من التثليثات الزائفة ذات النقاط. كما قدم باحثو الهندسة الحسابية خوارزميات لحصر جميع التثليثات الزائفة ذات النقاط لمجموعة نقاط في وقت قصير لكل تثليث زائف. ^{[ 11 ]}

• منحنى العضلة الدالية
• مثلث دائري