متعدد السطوح المحدب

في كتابه "المضلعات المحدبة" ، يُعرّف غرونباوم المضلع المحدب بأنه مجموعة محدبة مضغوطة ذات عدد محدود من النقاط المتطرفة :

مجموعة${\displaystyle K}$ل${\displaystyle \mathbb {R} ^{n}}$تكون محدبة إذا كان لكل زوج من النقاط المختلفة${\displaystyle a}$،${\displaystyle b}$في${\displaystyle K}$، الجزء المغلق ذو النهايات${\displaystyle a}$و${\displaystyle b}$يحتوي على${\displaystyle K}$.

هذا يُعادل تعريف متعدد السطوح المحدب المحدود بأنه الغلاف المحدب لمجموعة منتهية من النقاط، حيث يجب أن تحتوي هذه المجموعة المنتهية على مجموعة النقاط القصوى لمتعدد السطوح. يُسمى هذا التعريف تمثيل الرؤوس ( تمثيل V أو وصف V ). ^{[ 1 ]} بالنسبة لمتعدد السطوح المحدب المضغوط، يكون وصف V الأدنى فريدًا، ويُعطى بمجموعة رؤوس متعدد السطوح. ^{[ 1 ]} يُسمى متعدد السطوح المحدب متعدد سطوح صحيحًا إذا كانت جميع إحداثيات رؤوسه أعدادًا صحيحة.

يمكن تعريف متعدد السطوح المحدب بأنه تقاطع عدد محدود من أنصاف الفضاءات. يُسمى هذا التعريف تمثيل نصف الفضاء ( تمثيل-H أو وصف-H ). ^{[ 1 ]} يوجد عدد لا نهائي من أوصاف-H لمتعدد السطوح المحدب. مع ذلك، بالنسبة لمتعدد السطوح المحدب كامل الأبعاد، يكون وصف-H الأدنى فريدًا في الواقع، ويُعطى بمجموعة أنصاف الفضاءات التي تُحدد الأوجه . ^{[ 1 ]}

يمكن كتابة نصف الفضاء المغلق على شكل متباينة خطية : ^{[ 1 ]}

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq b}$

أين${\displaystyle n}$يمثل بُعد الفضاء الذي يحتوي على متعدد السطوح قيد الدراسة. وبالتالي، يمكن اعتبار متعدد السطوح المحدب المغلق مجموعة حلول نظام المتباينات الخطية التالية :

${\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leq \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leq \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leq \;&&&b_{m}\\\end{alignedat}}}$

أين${\displaystyle m}$يمثل عدد أنصاف الفضاءات التي تحدد متعدد السطوح. ويمكن كتابة ذلك بإيجاز على شكل متباينة المصفوفة التالية :

${\displaystyle Ax\leq b}$

أين${\displaystyle A}$هو${\displaystyle m\times n}$مصفوفة،${\displaystyle x}$هو${\displaystyle n\times 1}$متجه عمودي إحداثياته ​​هي المتغيرات${\displaystyle x_{1}}$ل${\displaystyle x_{n}}$، و${\displaystyle b}$هو${\displaystyle m\times 1}$متجه عمودي إحداثياته ​​هي الجوانب اليمنى${\displaystyle b_{1}}$ل${\displaystyle b_{m}}$من المتباينات العددية.

يتم تعريف متعدد السطوح المحدب المفتوح بنفس الطريقة، مع استخدام المتباينات الصارمة في الصيغ بدلاً من المتباينات غير الصارمة.

معاملات كل صف من${\displaystyle A}$و${\displaystyle b}$تتوافق هذه القيم مع معاملات المتباينة الخطية التي تحدد نصف الفضاء المعني. وبالتالي، يتوافق كل صف في المصفوفة مع مستوى فائق داعم للمضلع، وهو مستوى فائق يحيط بنصف فضاء يحتوي على المضلع. إذا تقاطع مستوى فائق داعم مع المضلع، يُسمى مستوى فائق محيط (لأنه مستوى فائق داعم، فلا يمكنه أن يتقاطع مع المضلع إلا عند حدوده).

يفترض التعريف السابق أن متعدد السطوح كامل الأبعاد. في هذه الحالة، توجد مجموعة دنيا فريدة من المتباينات المحددة (حتى الضرب في عدد موجب). تُسمى المتباينات التي تنتمي إلى هذه المجموعة الدنيا الفريدة بالمتباينات الأساسية . تُسمى مجموعة نقاط متعدد السطوح التي تحقق متباينة أساسية مع المساواة بالوجه .

إذا لم يكن متعدد السطوح كامل الأبعاد، فإن حلول المعادلة${\displaystyle Ax\leq b}$تقع في فضاء فرعي أفيني مناسب من${\displaystyle \mathbb {R} ^{n}}$ويمكن دراسة متعدد السطوح ككائن في هذا الفضاء الجزئي. في هذه الحالة، توجد معادلات خطية تحققها جميع نقاط متعدد السطوح. ولا يؤدي إضافة إحدى هذه المعادلات إلى أي من المتباينات المحددة إلى تغيير متعدد السطوح. لذلك، بشكل عام، لا توجد مجموعة دنيا فريدة من المتباينات تحدد متعدد السطوح.

بشكل عام، لا يشترط أن يكون تقاطع أنصاف الفضاءات محدودًا. مع ذلك، إذا رغبنا في تعريف مكافئ لتعريف الغلاف المحدب، فيجب اشتراط التحديد صراحةً.

يُوفر التمثيلان معًا طريقة فعّالة لتحديد ما إذا كان متجه مُعطى مُضمنًا في مُضلع محدب مُعين: لإثبات أنه مُضمن في المُضلع، يكفي تقديمه كتركيبة محدبة لرؤوس المُضلع (يُستخدم وصف V)؛ ولإثبات أنه غير مُضمن في المُضلع، يكفي تقديم مُتباينة تعريفية واحدة يُخالفها. ^{[ 5 ] : 256}

تكمن إحدى النقاط الدقيقة في التمثيل باستخدام المتجهات في أن عدد المتجهات قد يكون أُسّيًا بالنسبة للبعد، لذا قد يكون إثبات وجود متجه في متعدد السطوح طويلًا أُسّيًا. لحسن الحظ، تضمن نظرية كاراثيودوري أن كل متجه في متعدد السطوح يمكن تمثيله بما لا يزيد عن d + 1 متجهًا مُعرِّفًا، حيث d هو بُعد الفضاء.

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

وجه متعدد السطوح المحدب هو أي تقاطع بين متعدد السطوح ونصف فضاء بحيث لا تقع أي من النقاط الداخلية لمتعدد السطوح على حدود نصف الفضاء . وبصورة مكافئة، الوجه هو مجموعة النقاط التي تحقق المساواة في متباينة صحيحة معينة لمتعدد السطوح. ^{[ 5 ] : 258}

إذا كان متعدد الأوجه ذو أبعاد d ، فإن أوجهه هي وجوهه ذات الأبعاد ( d - 1)، ورؤوسه هي وجوهه ذات الأبعاد 0، وحوافه هي وجوهه ذات الأبعاد 1، ونتوءاته هي وجوهه ذات الأبعاد ( d - 2).    

بفرض وجود متعدد سطوح محدب P معرف بواسطة متباينة المصفوفة${\displaystyle Ax\leq b}$إذا كان كل صف في المصفوفة A يقابل مستوىً فائقًا محيطًا به، وكان مستقلًا خطيًا عن الصفوف الأخرى، فإن كل وجه من أوجه P يقابل صفًا واحدًا فقط من A ، والعكس صحيح، طالما تحققت المساواة. كل نقطة على وجه معين ستحقق المساواة الخطية للصف المقابل في المصفوفة. (قد تحقق المساواة في صفوف أخرى أو لا ). وبالمثل، كل نقطة على حافة ستحقق المساواة في صفين من صفوف A.

بشكل عام، يحقق الوجه ذو البعد ( n − j ) المساواة في j صفوف محددة من المصفوفة A. تشكل هذه الصفوف أساسًا للوجه. هندسيًا، يعني هذا أن الوجه هو مجموعة النقاط على متعدد السطوح التي تقع في تقاطع j من المستويات الفائقة المحيطة بمتعدد السطوح.  

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

يُطلق على شكلين متعددي الوجوه اسم متماثلين توافقياً إذا كانت شبكات وجوههما متماثلة .

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

المضلع المحدب، كأي مجموعة جزئية محدبة مضغوطة من Rⁿ ^، متماثل شكليًا مع كرة مغلقة . ^{[ 11 ]} لنرمز إلى بُعد المضلع بـ m . إذا كان المضلع كامل الأبعاد، فإن m = n . بالتالي، فإن المضلع المحدب هو متعدد شعب ذو m بُعد بحدود، وخاصيته الأويلرية تساوي 1، ومجموعته الأساسية تافهة. حدود المضلع المحدب متماثلة شكليًا مع كرة ذات ( m - 1) بُعد . خاصية أويلر للحدود تساوي 0 عندما يكون m زوجيًا، و2 عندما يكون m فرديًا . يمكن أيضًا اعتبار الحدود تجزئة لفضاء كروي ذي ( m - 1) بُعد ، أي كبلاط كروي .    

يمكن تحليل متعدد السطوح المحدب إلى مركب تبسيطي ، أو اتحاد من التبسيطات ، يحقق خصائص معينة.

بفرض وجود متعدد سطوح محدب ذي بُعد r ، يُعرَّف مُجسم بسيط من الرتبة r بأنه مجموعة جزئية من رؤوسه تحتوي على ( r + 1) نقطة مستقلة خطيًا . من الممكن تكوين مجموعة من المجموعات الجزئية بحيث يكون اتحاد المجسمات البسيطة المتناظرة مساويًا لـ P ، ويكون تقاطع أي مجسمين بسيطين إما فارغًا أو مُجسمًا بسيطًا ذا بُعد أقل. يُعد هذا التفكيك البسيط أساسًا للعديد من طرق حساب حجم متعدد السطوح المحدب، نظرًا لسهولة حساب حجم المُجسم البسيط باستخدام صيغة رياضية. ^{[ 12 ]}

يمكن تقسيم كل متعدد السطوح المحدب المنتظم ( الجسم الأفلاطوني ) إلى عدد زوجي من الحالات من مخططه المتعامد المميز .

تختلف فائدة التمثيلات المختلفة للمضلع المحدب، لذا يُعدّ بناء أحد هذه التمثيلات بمعرفة تمثيل آخر مشكلةً مهمة. تُعرف مشكلة بناء تمثيل V بمشكلة تعداد الرؤوس ، بينما تُعرف مشكلة بناء تمثيل H بمشكلة تعداد الأوجه . في حين أن مجموعة رؤوس المضلع المحدب المحدود تُعرّفه بشكلٍ فريد، إلا أنه من المهم في تطبيقاتٍ عديدة معرفة المزيد عن البنية التوافقية للمضلع، أي شبكة أوجهه. وتتناول خوارزميات الغلاف المحدب المختلفة كلاً من تعداد الأوجه وبناء شبكة الأوجه.

في الحالة المستوية، أي بالنسبة للمضلع المحدب ، فإن مشكلتي تعداد الأوجه والرؤوس تتلخصان في ترتيب الرؤوس (أو الحواف) حول الغلاف المحدب. وتكون هذه مهمة بسيطة عندما يتم تحديد المضلع المحدب بالطريقة التقليدية للمضلعات ، أي من خلال التسلسل المرتب لرؤوسه.${\displaystyle v_{1},\dots ,v_{m}}$عندما تكون قائمة الرؤوس (أو الحواف) المدخلة غير مرتبة، يصبح التعقيد الزمني للمسائل O ( m  log m ). ^{[ 13 ]} ويُعرف حد أدنى مطابق في نموذج شجرة القرار الجبرية للحساب. ^{[ 14 ]} 

تمت دراسة مهمة حساب حجم متعدد السطوح المحدب في مجال الهندسة الحسابية . يمكن حساب الحجم تقريبًا ، على سبيل المثال، باستخدام تقنية تقريب حجم متعدد السطوح المحدب ، عند توفر قاعدة بيانات عضوية . أما بالنسبة للحساب الدقيق ، فإن إحدى العقبات تكمن في أنه عند إعطاء تمثيل لمتعدد السطوح المحدب كنظام معادلات من المتباينات الخطية ، قد يكون لحجم متعدد السطوح طول بتات غير متعدد الحدود في هذا التمثيل. ^{[ 15 ]}