الوجوه المقطوعة ووجوه المكعبات للبوليطوبات متعددة القطع المرفوعة

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