مجموعة محدبة بشكل متكامل

المجموعة المحدبة المتكاملة هي النظير الهندسي المنفصل لمفهوم المجموعة المحدبة في الهندسة.

مجموعة جزئية X من شبكة الأعداد الصحيحة${\displaystyle \mathbb {Z} ^{n}}$تكون محدبة بشكل متكامل إذا كان من الممكن التعبير عن أي نقطة y في الغلاف المحدب لـ X على أنها تركيبة محدبة من نقاط X التي هي "قريبة" من y ، حيث تعني "قريبة" أن المسافة بين كل إحداثيين أقل من 1. ^{[ 1 ]}

ليكن X مجموعة جزئية من${\displaystyle \mathbb {Z} ^{n}}$.

لنرمز بـ ch( X ) إلى الغلاف المحدب للمجموعة X. لاحظ أن ch( X ) هي مجموعة جزئية من${\displaystyle \mathbb {R} ^{n}}$، لأنها تحتوي على جميع النقاط الحقيقية التي هي عبارة عن تركيبات محدبة للنقاط الصحيحة في X.

لأي نقطة y في${\displaystyle \mathbb {R} ^{n}}$، نرمز إلى near( y )  := { z in${\displaystyle \mathbb {Z} ^{n}}$| | z _i - y _i | < 1 لجميع i في {1,..., n } }. هذه هي النقاط الصحيحة التي تعتبر "قريبة" من النقطة الحقيقية y .

مجموعة جزئية X من${\displaystyle \mathbb {Z} ^{n}}$يُطلق عليها اسم محدبة تكاملياً إذا كانت كل نقطة y في ch( X ) موجودة أيضاً في ch( X ∩ near( y )). ^{[ 2 ]}

لنفترض أن n = 2 ولنفترض أن X = { (0,0), (1,0), (2,0), (2,1) }. يحتوي غلافها المحدب ch( X ) على سبيل المثال على النقطة y = (1.2, 0.5).

النقاط الصحيحة القريبة من y هي near( y ) = {(1,0), (2,0), (1,1), (2,1)}. لذا ، X ∩ near( y ) = {(1,0), (2,0), (2,1)}. لكن y لا تنتمي إلى ch( X ∩ near( y )). انظر الصورة على اليمين.

لذلك فإن X ليس محدبًا بشكل متكامل. ^{[ 1 ]}

في المقابل، فإن المجموعة Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } محدبة بشكل متكامل.

أظهر إيمورا وموروتا وتامورا ^{[ 3 ] الخاصية التالية للمجموعة المحدبة بشكل متكامل.}

يترك${\displaystyle X\subset \mathbb {Z} ^{n}}$لتكن X مجموعة محدبة تكاملية منتهية. يوجد تثليث لـ ch( X ) يكون تكامليًا ، أي:

• رؤوس التثليث هي رؤوس X ؛
• تقع رؤوس كل مُجَسَّم بسيط من التثليث في نفس "الخلية" (مكعب فائق طول ضلعه 1) من الشبكة الصحيحة${\displaystyle \mathbb {Z} ^{n}}$.

إن مجموعة المثال X ليست محدبة بشكل متكامل، وفي الواقع فإن ch( X ) لا تقبل التثليث المتكامل: كل تثليث لـ ch( X ) إما أن يضيف رؤوسًا ليست في X ، أو أن يتضمن أشكالًا بسيطة غير موجودة في خلية واحدة.

في المقابل، فإن المجموعة Y = { (0,0), (1,0), (2,0), (1,1), (2,1) } محدبة تكاملياً، وتسمح بالفعل بتثليث تكاملي، على سبيل المثال باستخدام الأشكال البسيطة الثلاثة {(0,0),(1,0),(1,1)} و {(1,0),(2,0),(2,1)} و {(1,0),(1,1),(2,1)}. انظر الصورة على اليمين.