उत्तल पॉलीटॉप

एक 3-आयामी उत्तल पॉलीटॉप

एक उत्तल पॉलीटॉप पॉलीटॉप का विशेष मामला है, जिसमें अतिरिक्त गुण होते हैं कि यह उत्तल सेट भी होता है $n$-आयामी यूक्लिडियन अंतरिक्ष $\mathbb {R} ^{n}$. अधिकांश ग्रंथ बंधे हुए सेट उत्तल पॉलीटॉप के लिए पॉलीटॉप शब्द का उपयोग करें, और अधिक सामान्य, संभवतः अबाधित वस्तु के लिए पॉलीहेड्रॉन शब्द का उपयोग करें। अन्य (इस लेख सहित) पॉलीटोप्स को असीमित होने की अनुमति दें। बाउंडेड/अनबाउंड कॉन्वेक्स पॉलीटोप का उपयोग नीचे तब किया जाएगा जब बाउंडनेस चर्चा किए गए मुद्दे के लिए महत्वपूर्ण हो। फिर भी अन्य ग्रंथ इसकी सीमा के साथ उत्तल पॉलीटॉप की पहचान करते हैं।

उत्तल बहुशीर्ष गणित की विभिन्न शाखाओं और अनुप्रयुक्त क्षेत्रों दोनों में महत्वपूर्ण भूमिका निभाते हैं, विशेष रूप से रैखिक प्रोग्रामिंग में।

ग्रुनबाम की प्रभावशाली पाठ्यपुस्तकों मेंऔर ज़िग्लरविषय पर, साथ ही असतत ज्यामिति में कई अन्य ग्रंथों में, उत्तल पॉलीटोप्स को अक्सर पॉलीटोप्स कहा जाता है। ग्रुनबाउम बताते हैं कि यह केवल उत्तल शब्द की अंतहीन पुनरावृत्ति से बचने के लिए है, और यह कि चर्चा को केवल उत्तल विविधता (पृष्ठ 51) पर लागू करने के रूप में समझा जाना चाहिए।

एक पॉलीटॉप को पूर्ण-आयामी कहा जाता है यदि यह है $n$-आयामी वस्तु में $\mathbb {R} ^{n}$.

उदाहरण

• बाध्य उत्तल पॉलीटोप्स के कई उदाहरण लेख पॉलीहेड्रॉन में पाए जा सकते हैं।
• 2-आयामी मामले में पूर्ण-आयामी उदाहरण आधा-विमान, दो समानांतर रेखाओं के बीच पट्टी, कोण आकार (दो गैर-समानांतर अर्ध-विमानों का प्रतिच्छेदन), उत्तल बहुभुज श्रृंखला द्वारा परिभाषित आकृति है इसके सिरों से जुड़ी दो किरणें (ज्यामिति) और उत्तल बहुभुज।
• एक असीमित उत्तल पॉलीटोप के विशेष मामले दो समानांतर हाइपरप्लेन के बीच स्लैब (ज्यामिति), दो गैर-समानांतर हाफ-स्पेस (ज्यामिति) द्वारा परिभाषित वेज हैं। हाफ-स्पेस, पॉलीहेड्रल सिलेंडर (अनंत प्रिज्म (ज्यामिति)), और बहुफलकीय शंकु (अनंत शंकु) सामान्य बिंदु से गुजरने वाली तीन या अधिक अर्ध-रिक्तियों द्वारा परिभाषित।

परिभाषाएँ

हाथ में समस्या के लिए अधिक उपयुक्त क्या है, इस पर निर्भर करते हुए उत्तल पॉलीटॉप को कई तरीकों से परिभाषित किया जा सकता है। ग्रुनबाम की परिभाषा अंतरिक्ष में बिंदुओं के उत्तल सेट के संदर्भ में है। अन्य महत्वपूर्ण परिभाषाएँ हैं: अर्ध-स्थान (ज्यामिति) के प्रतिच्छेदन (सेट सिद्धांत) के रूप में | अर्ध-स्थान (आधा-स्थान प्रतिनिधित्व) और बिंदुओं के सेट के उत्तल पतवार के रूप में (शीर्ष प्रतिनिधित्व)।

वर्टेक्स प्रतिनिधित्व (उत्तल पतवार)

अपनी पुस्तक उत्तल पॉलीटोप्स में, ग्रुनबाम उत्तल पॉलीटॉप को 'कॉम्पैक्ट स्पेस उत्तल सेट के साथ चरम बिंदुओं की सीमित संख्या' के रूप में परिभाषित करता है:

एक सेट $K$ का $\mathbb {R} ^{n}$ उत्तल है अगर, अलग-अलग बिंदुओं की प्रत्येक जोड़ी के लिए $a$, $b$ में $K$, समापन बिंदु के साथ बंद खंड $a$ तथा $b$ के भीतर निहित है $K$.

यह परिमित उत्तल पॉलीटॉप को बिंदुओं के परिमित सेट के उत्तल पतवार के रूप में परिभाषित करने के बराबर है, जहां परिमित सेट में पॉलीटॉप के चरम बिंदुओं का सेट होना चाहिए। इस तरह की परिभाषा को शीर्ष प्रतिनिधित्व (वी-प्रतिनिधित्व या वी-विवरण) कहा जाता है। कॉम्पैक्ट उत्तल पॉलीटॉप के लिए, न्यूनतम वी-विवरण अद्वितीय है और यह पॉलीटॉप के वर्टेक्स (ज्यामिति) के सेट द्वारा दिया गया है।एक उत्तल पॉलीटॉप को अभिन्न पॉलीटॉप कहा जाता है यदि इसके सभी कोने पूर्णांक निर्देशांक होते हैं।

आधी जगहों का चौराहा

एक उत्तल पॉलीटॉप को अर्ध-स्थानों की परिमित संख्या के प्रतिच्छेदन के रूप में परिभाषित किया जा सकता है। ऐसी परिभाषा को आधा स्थान प्रतिनिधित्व (एच-प्रतिनिधित्व या एच-विवरण) कहा जाता है। उत्तल पॉलीटॉप के असीम रूप से कई एच-विवरण मौजूद हैं। हालांकि, पूर्ण-आयामी उत्तल पॉलीटॉप के लिए, न्यूनतम एच-विवरण वास्तव में अद्वितीय है और यह पहलू (ज्यामिति) के सेट द्वारा दिया जाता है - हाफस्पेस को परिभाषित करता है।

एक बंद अर्ध-स्थान को रैखिक असमानता के रूप में लिखा जा सकता है:

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

कहाँ पे $n$ विचाराधीन पॉलीटॉप वाले स्थान का आयाम है। इसलिए, बंद उत्तल पॉलीटॉप को रैखिक असमानताओं की प्रणाली के समाधान के सेट के रूप में माना जा सकता है:

${\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}}$

कहाँ पे $m$ पॉलीटॉप को परिभाषित करने वाले आधे-स्थानों की संख्या है। इसे संक्षेप में मैट्रिक्स (गणित) असमानता के रूप में लिखा जा सकता है:

$Ax\leq b$

कहाँ पे $A$ $m\times n$ आव्यूह, $x$ $n\times 1$ स्तंभ सदिश जिसके निर्देशांक चर हैं $x_{1}$ प्रति $x_{n}$, तथा $b$ $m\times 1$ कॉलम वेक्टर जिसका निर्देशांक दाहिनी ओर है $b_{1}$ प्रति $b_{m}$ अदिश असमानताओं की।

एक खुले उत्तल पॉलीटोप को उसी तरह परिभाषित किया गया है, जिसमें गैर-सख्त लोगों के बजाय सूत्रों में सख्त असमानताओं का उपयोग किया गया है।

की प्रत्येक पंक्ति के गुणांक $A$ तथा $b$ संबंधित अर्ध-स्थान को परिभाषित करने वाली रैखिक असमानता के गुणांक के अनुरूप है। इसलिए, मैट्रिक्स में प्रत्येक पंक्ति पॉलीटॉप के सहायक हाइपरप्लेन से मेल खाती है, हाइपरप्लेन आधे स्थान को बांधता है जिसमें पॉलीटॉप होता है। यदि सहायक हाइपरप्लेन भी पॉलीटॉप को काटता है, तो इसे बाउंडिंग हाइपरप्लेन कहा जाता है (चूंकि यह सहायक हाइपरप्लेन है, यह केवल पॉलीटॉप की सीमा पर पॉलीटोप को काट सकता है)।

पूर्वगामी परिभाषा मानती है कि पॉलीटॉप पूर्ण-आयामी है। इस मामले में, असमानताओं को परिभाषित करने का 'अद्वितीय' न्यूनतम सेट है (एक सकारात्मक संख्या से गुणा तक)। इस अनूठी न्यूनतम प्रणाली से संबंधित असमानताओं को आवश्यक कहा जाता है। पॉलीटोप के बिंदुओं का समूह जो समानता के साथ आवश्यक असमानता को संतुष्ट करता है, पहलू कहलाता है।

यदि पॉलीटॉप पूर्ण-आयामी नहीं है, तो समाधान $Ax\leq b$ के उचित संबंध उप-स्थान में झूठ बोलना $\mathbb {R} ^{n}$ और इस उप-स्थान में वस्तु के रूप में पॉलीटॉप का अध्ययन किया जा सकता है। इस मामले में, वहाँ रैखिक समीकरण मौजूद हैं जो पॉलीटॉप के सभी बिंदुओं से संतुष्ट हैं। इन समीकरणों में से किसी को परिभाषित असमानताओं में जोड़ने से पॉलीटॉप नहीं बदलता है। इसलिए, सामान्य तौर पर पॉलीटोप को परिभाषित करने वाली असमानताओं का कोई अनूठा न्यूनतम सेट नहीं है।

आम तौर पर मनमाना अर्ध-स्थानों के चौराहे को बाध्य करने की आवश्यकता नहीं होती है। हालांकि अगर कोई उत्तल हल के बराबर परिभाषा चाहता है, तो बाध्यता स्पष्ट रूप से आवश्यक होनी चाहिए।

=== विभिन्न अभ्यावेदन === का उपयोग करना दो अभ्यावेदन साथ यह तय करने का कुशल तरीका प्रदान करते हैं कि क्या दिए गए वेक्टर को दिए गए उत्तल पॉलीटॉप में शामिल किया गया है: यह दिखाने के लिए कि यह पॉलीटॉप में है, यह पॉलीटोप वर्टिस (वी-विवरण) के उत्तल संयोजन के रूप में प्रस्तुत करने के लिए पर्याप्त है प्रयोग किया जाता है); यह दिखाने के लिए कि यह पॉलीटॉप में नहीं है, यह एकल परिभाषित असमानता को प्रस्तुत करने के लिए पर्याप्त है जिसका यह उल्लंघन करता है। सदिशों द्वारा प्रतिनिधित्व में सूक्ष्म बिंदु यह है कि सदिशों की संख्या आयाम में घातीय हो सकती है, इसलिए प्रमाण है कि सदिश पॉलीटॉप में है, वह घातीय रूप से लंबा हो सकता है। सौभाग्य से, कैराथियोडोरी का प्रमेय (उत्तल हल) | कैराथियोडोरी का प्रमेय गारंटी देता है कि पॉलीटॉप में प्रत्येक वेक्टर को अधिकतम डी+1 परिभाषित वैक्टर द्वारा दर्शाया जा सकता है, जहां डी अंतरिक्ष का आयाम है।

असीमित पॉलीटोप्स का प्रतिनिधित्व

एक असीमित पॉलीटॉप (कभी-कभी कहा जाता है: पॉलीहेड्रॉन) के लिए, एच-विवरण अभी भी मान्य है, लेकिन वी-विवरण को बढ़ाया जाना चाहिए। थिओडोर मोट्ज़किन (1936) ने साबित किया कि किसी भी असीमित पॉलीटोप को बंधे हुए पॉलीटोप और उत्तल शंकु के योग के रूप में दर्शाया जा सकता है। दूसरे शब्दों में, असंबद्ध पॉलीटोप में प्रत्येक सदिश अपने शीर्षों (इसके परिभाषित बिंदु) का उत्तल योग है, साथ ही इसके अनंत किनारों (इसकी परिभाषित किरणें) के यूक्लिडियन सदिशों का शंक्वाकार योग है। इसे परिमित आधार प्रमेय कहा जाता है।

गुण

प्रत्येक (बाध्य) उत्तल पॉलीटॉप सिंप्लेक्स की छवि है, क्योंकि प्रत्येक बिंदु (अंततः कई) शीर्षों का उत्तल संयोजन है। हालांकि, पॉलीटॉप सामान्य रूप से सरलताओं के लिए आइसोमोर्फिक नहीं हैं। यह वेक्टर रिक्त स्थान और रैखिक संयोजन के मामले के विपरीत है, प्रत्येक परिमित-आयामी वेक्टर स्थान न केवल छवि है, बल्कि वास्तव में आइसोमोर्फिक है, कुछ आयाम के यूक्लिडियन स्थान (या अन्य क्षेत्रों पर एनालॉग)।

चेहरा जाली

Main article: abstract polytope

एक उत्तल पॉलीटॉप का चेहरा (ज्यामिति) आधा स्थान (ज्यामिति) के साथ पॉलीटॉप का कोई चौराहे है, जैसे कि पॉलीटॉप के आंतरिक बिंदुओं में से कोई भी आधे स्थान की सीमा पर नहीं है। समतुल्य रूप से, चेहरा पॉलीटॉप की कुछ वैध असमानता में समानता देने वाले बिंदुओं का समूह है। यदि पॉलीटोप डी-आयामी है, तो इसके पहलू (गणित) इसके (डी − 1)-आयामी चेहरे हैं, इसके शीर्ष (ज्यामिति) इसके 0-आयामी चेहरे हैं, इसके किनारे (ज्यामिति) इसके 1-आयामी चेहरे हैं, और इसके कटक (ज्यामिति) इसके (d − 2)-विमीय फलक हैं।

मैट्रिक्स असमानता द्वारा परिभाषित उत्तल पॉलीटॉप पी दिया गया $Ax\leq b$, यदि A में प्रत्येक पंक्ति बाउंडिंग हाइपरप्लेन से मेल खाती है और अन्य पंक्तियों से रैखिक रूप से स्वतंत्र है, तो P का प्रत्येक पहलू A की ठीक पंक्ति से मेल खाता है, और इसके विपरीत। किसी दिए गए पहलू पर प्रत्येक बिंदु मैट्रिक्स में संबंधित पंक्ति की रैखिक समानता को संतुष्ट करेगा। (यह अन्य पंक्तियों में समानता को संतुष्ट कर भी सकता है और नहीं भी)। इसी प्रकार, रिज पर प्रत्येक बिंदु ए की दो पंक्तियों में समानता को पूरा करेगा।

एक हस आरेख के रूप में तैयार वर्ग पिरामिड का चेहरा जाली; जाली में प्रत्येक चेहरे को उसके शीर्ष सेट द्वारा लेबल किया जाता है।

सामान्य तौर पर, (एन − जे)-आयामी चेहरा ए की जे विशिष्ट पंक्तियों में समानता को संतुष्ट करता है। ये पंक्तियाँ चेहरे का 'आधार' बनाती हैं। ज्यामितीय रूप से बोलना, इसका मतलब है कि चेहरा पॉलीटोप पर बिंदुओं का समूह है जो पॉलीटोप के बाउंडिंग हाइपरप्लेन के जे के चौराहे पर स्थित है।

एक उत्तल पॉलीटॉप के चेहरे इस प्रकार यूलेरियन पोसेट जाली (ऑर्डर) बनाते हैं, जिसे इसका 'फेस लैटिस' कहा जाता है, जहां आंशिक क्रम चेहरों के सेट द्वारा होता है। ऊपर दिए गए चेहरे की परिभाषा पॉलीटॉप और खाली सेट दोनों को चेहरे के रूप में माना जाता है, यह सुनिश्चित करता है कि चेहरे की प्रत्येक जोड़ी में शामिल हो और चेहरे की जाली में मिल जाए। संपूर्ण पॉलीटॉप जाली का अद्वितीय अधिकतम तत्व है, और खाली सेट, जिसे प्रत्येक पॉलीटॉप का (-1) -डायमेंशनल फेस (एक 'नल पॉलीटोप') माना जाता है, जाली का अद्वितीय न्यूनतम तत्व है।

दो पॉलीटोप्स को 'कॉम्बिनेटरियल आइसोमोर्फिक' कहा जाता है यदि उनके चेहरे की जाली आइसोमोर्फिज्म हैं।

'पॉलीटॉप ग्राफ' ('पॉलीटोपल ग्राफ', 'पॉलीटॉप का ग्राफ', '1-कंकाल') केवल पॉलीटॉप के कोने और किनारों का सेट है, जो उच्च-आयामी चेहरों की अनदेखी करता है। उदाहरण के लिए, पॉलीहेड्रल ग्राफ त्रि-आयामी पॉलीटॉप का पॉलीटॉप ग्राफ है। हस्लर व्हिटनी के परिणामस्वरूप त्रि-आयामी पॉलीटॉप का चेहरा जाली इसके ग्राफ द्वारा निर्धारित किया जाता है। मनमाना आयाम के सरल पॉलीटोप्स के लिए भी यही सच है (ब्लाइंड एंड मणि-लेवित्स्का 1987, मीका पर्ल्स का अनुमान साबित करना)। कलाई (1988) अद्वितीय सिंक ओरिएंटेशन के आधार पर सरल प्रमाण देता है। क्योंकि इन पॉलीटॉप्स के चेहरे की जाली उनके ग्राफ़ द्वारा निर्धारित की जाती है, यह तय करने की समस्या है कि क्या दो त्रि-आयामी या सरल उत्तल पॉलीटोप्स कॉम्बीनेटरियल आइसोमोर्फिक हैं, ग्राफ़ आइसोमोर्फिज़्म समस्या के विशेष मामले के रूप में समान रूप से तैयार किए जा सकते हैं। हालांकि, इन समस्याओं को विपरीत दिशा में अनुवाद करना भी संभव है, यह दर्शाता है कि पोलीटॉप समरूपता परीक्षण ग्राफ-समरूपता पूर्ण है।

सांस्थितिक गुण

एक उत्तल पॉलीटोप, आर के किसी भी कॉम्पैक्ट उत्तल उपसमुच्चय की तरहⁿ, बंद गेंद (गणित) के लिए होमोमोर्फिज्म है। मान लीजिए m पॉलीटॉप के आयाम को निरूपित करता है। यदि पॉलीटॉप पूर्ण-आयामी है, तो एम = एन। इसलिए उत्तल पॉलीटॉप सीमा के साथ एम-आयामी मैनिफोल्ड (गणित) है, इसकी यूलर विशेषता 1 है, और इसका मौलिक समूह तुच्छ है। उत्तल पॉलीटॉप की सीमा n-sphere|(m − 1)-sphere के लिए होमियोमॉर्फिक है। सम m के लिए बाउंड्री की यूलर विशेषता 0 और विषम m के लिए 2 है। सीमा को (m − 1)-विमीय दीर्घवृत्तीय स्थान के टेसलेशन के रूप में भी माना जा सकता है — यानी गोलाकार खपरैल के रूप में।

साधारण अपघटन

कुछ गुणों को संतुष्ट करते हुए, उत्तल पॉलीटॉप को साधारण जटिल, या सिंप्लेक्स के संघ में विघटित किया जा सकता है।

एक उत्तल आर-आयामी पॉलीटॉप पी दिया गया है, इसके शीर्षों का उपसमुच्चय जिसमें (आर+1) आत्मीयता से स्वतंत्र बिंदु होते हैं, सिम्प्लेक्स | आर-सिम्प्लेक्स को परिभाषित करता है। उपसमुच्चय का संग्रह बनाना संभव है जैसे कि संबंधित सरलताओं का संघ पी के बराबर है, और किसी भी दो सरलताओं का चौराहे या तो खाली है या निम्न-आयामी सरल है। यह साधारण अपघटन उत्तल पॉलीटोप की मात्रा की गणना के लिए कई तरीकों का आधार है, क्योंकि सरल सूत्र की मात्रा आसानी से सूत्र द्वारा दी जाती है।

== उत्तल पॉलीटॉप == के लिए एल्गोरिदमिक समस्याएं

अभ्यावेदन का निर्माण

एक उत्तल पॉलीटॉप के विभिन्न अभ्यावेदन में अलग-अलग उपयोगिता होती है, इसलिए प्रतिनिधित्व का निर्माण महत्वपूर्ण समस्या है। वी-प्रतिनिधित्व के निर्माण की समस्या को शीर्ष गणना समस्या के रूप में जाना जाता है और एच-प्रतिनिधित्व के निर्माण की समस्या को पहलू गणना समस्या के रूप में जाना जाता है। जबकि बंधे हुए उत्तल पॉलीटॉप का वर्टेक्स सेट विशिष्ट रूप से इसे परिभाषित करता है, विभिन्न अनुप्रयोगों में पॉलीटोप की संयोजी संरचना के बारे में अधिक जानना महत्वपूर्ण है, अर्थात, इसके चेहरे की जाली के बारे में। विभिन्न उत्तल हल एल्गोरिदम पहलू गणना और चेहरे जाली निर्माण दोनों के साथ सौदा करते हैं।

प्लानर मामले में, यानी, उत्तल बहुभुज के लिए, उत्तल पतवार के चारों ओर ऑर्डरिंग वर्टिस (प्रतिक्रिया किनारों) के लिए दोनों पहलू और शीर्ष गणना समस्याएं होती हैं। यह तुच्छ कार्य है जब उत्तल बहुभुज को पारंपरिक तरीके से बहुभुजों के लिए निर्दिष्ट किया जाता है, अर्थात, इसके शीर्षों के क्रमबद्ध क्रम द्वारा $v_{1},\dots ,v_{m}$. जब शीर्षों (या किनारों) की इनपुट सूची अनियंत्रित होती है, तो समस्याओं की समय जटिलता बिग ओह नोटेशन (एम लॉग एम) बन जाती है। संगणना के बीजगणितीय निर्णय ट्री मॉडल में मैचिंग लोअर बाउंड जाना जाता है।

वॉल्यूम गणना

कम्प्यूटेशनल ज्यामिति के क्षेत्र में उत्तल पॉलीटॉप की मात्रा की गणना करने का कार्य अध्ययन किया गया है। वॉल्यूम की गणना सन्निकटन एल्गोरिथ्म की जा सकती है, उदाहरण के लिए, उत्तल आयतन सन्निकटन तकनीक का उपयोग करते हुए, जब सदस्यता ऑरेकल मशीन तक पहुँच होती है। सटीक एल्गोरिदम के लिए, बाधा यह है कि, जब रैखिक असमानता की समीकरण प्रणाली के रूप में उत्तल पॉलीटॉप का प्रतिनिधित्व दिया जाता है, तो पॉलीटॉप की मात्रा में थोड़ी-लंबाई हो सकती है जो इस प्रतिनिधित्व में बहुपद नहीं है।

यह भी देखें

• ओरिएंटेड मैट्रोइड
• नेफ पॉलीहेड्रॉन
• उत्तल पॉलीहेड्रा के लिए स्टीनिट्ज़ का प्रमेय

बाहरी संबंध

• Weisstein, Eric W. "Convex polygon". MathWorld.
• Weisstein, Eric W. "Convex polyhedron". MathWorld.
• Komei Fukuda, Polyhedral computation FAQ.