उत्तल पॉलीटॉप: Difference between revisions

Revision as of 23:12, 9 May 2023

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

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

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

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

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

उदाहरण

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

परिभाषाएँ

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

अक्षीय प्रतिनिधित्व (उत्तल आवरण)

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

एक समुच्चय

K

का

\mathbb {R} ^{n}

उत्तल है यदि, अलग-अलग बिंदुओं की प्रत्येक जोड़ी के लिए

a

,

b

में

K

, समापन बिंदु के साथ बंद खंड

a

तथा

b

के भीतर

K

निहित रहता है।

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

अर्धस्थानों का अंतःखण्ड

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

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

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}$ और इस उप-स्थान में वस्तु के रूप में पॉलीटॉप का अध्ययन किया जा सकता है। इस मामले में, वहाँ रैखिक समीकरण सम्मिलित हैं जो पॉलीटॉप के सभी बिंदुओं से संतुष्ट हैं। इस प्रकार इन समीकरणों में से किसी को परिभाषित असमानताओं में जोड़ने से पॉलीटॉप नहीं बदलता है। इसलिए, सामान्य तौर पर पॉलीटोप को परिभाषित करने वाली असमानताओं का कोई अनूठा न्यूनतम समुच्चय नहीं है।

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

विभिन्न अभ्यावेदन का उपयोग करना

दो अभ्यावेदन साथ यह तय करने का कुशल विधि प्रदान करते हैं कि क्या दिए गए वेक्टर को दिए गए उत्तल पॉलीटॉप में सम्मिलित किया गया है: यह दिखाने के लिए कि यह पॉलीटॉप में है, यह पॉलीटोप वर्टिस (वी-विवरण) के उत्तल संयोजन के रूप में प्रस्तुत करने के लिए पर्याप्त है प्रयोग किया जाता है); यह दिखाने के लिए कि यह पॉलीटॉप में नहीं है, यह एकल परिभाषित असमानता को प्रस्तुत करने के लिए पर्याप्त है जिसका यह उल्लंघन करता है।^[4]^: 256

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

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

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

गुण

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

फेस लैटिस

एक उत्तल पॉलीटॉप का फेस (ज्यामिति) आधा स्थान (ज्यामिति) के साथ पॉलीटॉप का कोई अंतःखण्ड है, जैसे कि पॉलीटॉप के आंतरिक बिंदुओं में से कोई भी आधे स्थान की सीमा पर नहीं है। इस कारण समतुल्य रूप से, फेस पॉलीटॉप की कुछ वैध असमानता में समानता देने वाले बिंदुओं का समूह है।^[4]^: 258

यदि पॉलीटोप डी-आयामी है, तो इसके पहलू (गणित) इसके (d − 1)-आयामी फेस हैं, इसके शीर्ष (ज्यामिति) इसके 0-आयामी फेस हैं, इसके किनारे (ज्यामिति) इसके 1-आयामी फेस हैं, और इसके कटक (ज्यामिति) इसके (d − 2)-विमीय फलक हैं।

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

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

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

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

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

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

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

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

साधारण अपघटन

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

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

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

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

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

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

आयतन की गणना

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

यह भी देखें

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

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Branko Grünbaum, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler, 2003, ISBN 0-387-40409-0, ISBN 978-0-387-40409-7, 466pp.
↑ ^2.0 ^2.1 Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Berlin, New York: Springer-Verlag.
↑ ^3.0 ^3.1 Mathematical Programming, by Melvyn W. Jeter (1986) ISBN 0-8247-7478-7, p. 68
↑ ^4.0 ^4.1 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
↑ Motzkin, Theodore (1936). रैखिक असमानताओं के सिद्धांत में योगदान (पीएचडी शोध प्रबंध). Jerusalem.{{cite book}}: CS1 maint: location missing publisher (link)
↑ Whitney, Hassler (1932). "सर्वांगसम रेखांकन और रेखांकन की कनेक्टिविटी". Amer. J. Math. 54 (1): 150–168. doi:10.2307/2371086. hdl:10338.dmlcz/101067. JSTOR 2371086.
↑ Blind, Roswitha; Mani-Levitska, Peter (1987), "Puzzles and polytope isomorphisms", Aequationes Mathematicae, 34 (2–3): 287–297, doi:10.1007/BF01830678, MR 0921106.
↑ Kalai, Gil (1988), "A simple way to tell a simple polytope from its graph", Journal of Combinatorial Theory, Ser. A, 49 (2): 381–383, doi:10.1016/0097-3165(88)90064-7, MR 0964396.
↑ Kaibel, Volker; Schwartz, Alexander (2003). "पॉलीटॉप आइसोमोर्फिज्म समस्याओं की जटिलता पर". Graphs and Combinatorics. 19 (2): 215–230. arXiv:math/0106093. doi:10.1007/s00373-002-0503-y. Archived from the original on 2015-07-21.
↑ Glen E. Bredon, Topology and Geometry, 1993, ISBN 0-387-97926-3, p. 56.
↑ Büeler, B.; Enge, A.; Fukuda, K. (2000). "Exact Volume Computation for Polytopes: A Practical Study". पॉलीटोप्स - कॉम्बिनेटरिक्स और कम्प्यूटेशन. p. 131. doi:10.1007/978-3-0348-8438-9_6. ISBN 978-3-7643-6351-2.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "33.3 Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 947–957. ISBN 0-262-03293-7.
↑ Yao, Andrew Chi Chih (1981), "A lower bound to finding convex hulls", Journal of the ACM, 28 (4): 780–787, doi:10.1145/322276.322289, MR 0677089; Ben-Or, Michael (1983), "Lower Bounds for Algebraic Computation Trees", Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 80–86, doi:10.1145/800061.808735.
↑ Lawrence, Jim (1991). "पॉलीटॉप मात्रा गणना". Mathematics of Computation (in English). 57 (195): 259–271. doi:10.1090/S0025-5718-1991-1079024-2. ISSN 0025-5718.

बाहरी संबंध

[grun-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Branko Grünbaum, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler, 2003, ISBN 0-387-40409-0, ISBN 978-0-387-40409-7, 466pp.

[zieg-2] 2.0 ^2.1 Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Berlin, New York: Springer-Verlag.

[Jeter-3] 3.0 ^3.1 Mathematical Programming, by Melvyn W. Jeter (1986) ISBN 0-8247-7478-7, p. 68

[lp-4] 4.0 ^4.1 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

[5] Motzkin, Theodore (1936). रैखिक असमानताओं के सिद्धांत में योगदान (पीएचडी शोध प्रबंध). Jerusalem.{{cite book}}: CS1 maint: location missing publisher (link)

[6] Whitney, Hassler (1932). "सर्वांगसम रेखांकन और रेखांकन की कनेक्टिविटी". Amer. J. Math. 54 (1): 150–168. doi:10.2307/2371086. hdl:10338.dmlcz/101067. JSTOR 2371086.

[7] Blind, Roswitha; Mani-Levitska, Peter (1987), "Puzzles and polytope isomorphisms", Aequationes Mathematicae, 34 (2–3): 287–297, doi:10.1007/BF01830678, MR 0921106.

[8] Kalai, Gil (1988), "A simple way to tell a simple polytope from its graph", Journal of Combinatorial Theory, Ser. A, 49 (2): 381–383, doi:10.1016/0097-3165(88)90064-7, MR 0964396.

[9] Kaibel, Volker; Schwartz, Alexander (2003). "पॉलीटॉप आइसोमोर्फिज्म समस्याओं की जटिलता पर". Graphs and Combinatorics. 19 (2): 215–230. arXiv:math/0106093. doi:10.1007/s00373-002-0503-y. Archived from the original on 2015-07-21.

[bredon-10] Glen E. Bredon, Topology and Geometry, 1993, ISBN 0-387-97926-3, p. 56.

[11] Büeler, B.; Enge, A.; Fukuda, K. (2000). "Exact Volume Computation for Polytopes: A Practical Study". पॉलीटोप्स - कॉम्बिनेटरिक्स और कम्प्यूटेशन. p. 131. doi:10.1007/978-3-0348-8438-9_6. ISBN 978-3-7643-6351-2.

[12] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "33.3 Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 947–957. ISBN 0-262-03293-7.

[13] Yao, Andrew Chi Chih (1981), "A lower bound to finding convex hulls", Journal of the ACM, 28 (4): 780–787, doi:10.1145/322276.322289, MR 0677089; Ben-Or, Michael (1983), "Lower Bounds for Algebraic Computation Trees", Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 80–86, doi:10.1145/800061.808735.

[14] Lawrence, Jim (1991). "पॉलीटॉप मात्रा गणना". Mathematics of Computation (in English). 57 (195): 259–271. doi:10.1090/S0025-5718-1991-1079024-2. ISSN 0025-5718.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 1: / Line 1: @@
 {{Short description|Convex hull of a finite set of points in a Euclidean space}}
-[[File:3dpoly.svg|thumb|right|एक 3-आयामी उत्तल पॉलीटॉप]]एक उत्तल पॉलीटॉप पॉलीटॉप का विशेष मामला है, जिसमें अतिरिक्त गुण होते हैं कि यह उत्तल सेट भी होता है <math>n</math>-आयामी यूक्लिडियन अंतरिक्ष <math>\mathbb{R}^n</math>. अधिकांश ग्रंथ<ref name=grun/><ref name=zieg>{{Citation
+[[File:3dpoly.svg|thumb|right|एक 3-आयामी उत्तल पॉलीटॉप]]उत्तल पॉलीटॉप मुख्यतः पॉलीटॉप की ऐसी विशेष स्थिति है, जिसमें अतिरिक्त गुण होते हैं इसका कारण यह हैं कि यह उत्तल समुच्चय द्वारा प्रदर्शित होता हैं इस कारण <math>n</math>-आयामी यूक्लिडियन अंतरिक्ष को <math>\mathbb{R}^n</math> के रूप में लिख सकते हैं। इस प्रकार अधिकांश ग्रंथों<ref name=grun/><ref name=zieg>{{Citation
 | last=Ziegler
 | first=Günter M.
@@ Line 9: / Line 9: @@
 | series=Graduate Texts in Mathematics
 | year=1995
-| volume=152}}.</ref> बंधे हुए सेट उत्तल पॉलीटॉप के लिए पॉलीटॉप शब्द का उपयोग करें, और अधिक सामान्य, संभवतः अबाधित वस्तु के लिए पॉलीहेड्रॉन शब्द का उपयोग करें। अन्य<ref name=Jeter>''Mathematical Programming'', by Melvyn W. Jeter (1986) {{ISBN|0-8247-7478-7}}, [https://books.google.com/books?id=ofrBsl61lq8C&pg=PA67 p. 68]</ref> (इस लेख सहित) पॉलीटोप्स को असीमित होने की अनुमति दें। बाउंडेड/अनबाउंड कॉन्वेक्स पॉलीटोप का उपयोग नीचे तब किया जाएगा जब बाउंडनेस चर्चा किए गए मुद्दे के लिए महत्वपूर्ण हो। फिर भी अन्य ग्रंथ इसकी सीमा के साथ उत्तल पॉलीटॉप की पहचान करते हैं।
+| volume=152}}.</ref> के माध्यम से बंधे हुए समुच्चयों को उत्तल पॉलीटॉप के लिए पॉलीटॉप शब्द का उपयोग करते हैं, और अधिक सामान्य रूप प्राप्त करने के लिए संभवतः अबाधित वस्तु के लिए पॉलीहेड्रॉन शब्द का उपयोग करते हैं। इस कारण किसी अन्य<ref name=Jeter>''Mathematical Programming'', by Melvyn W. Jeter (1986) {{ISBN|0-8247-7478-7}}, [https://books.google.com/books?id=ofrBsl61lq8C&pg=PA67 p. 68]</ref> (इस लेख सहित) पॉलीटोप्स को असीमित होने की अनुमति देते हैं। इस प्रकार बाउंडेड या अनबाउंड कॉन्वेक्स पॉलीटोप का उपयोग नीचे उस स्थिति में किया जाएगा जब बाउंडनेस द्वारा की गई चर्चा के कारण इन स्थितियों के लिए इसे महत्वपूर्ण माना जाता हो। फिर भी अन्य ग्रंथ इसकी सीमा के साथ उत्तल पॉलीटॉप की पहचान करते हैं।
-उत्तल बहुशीर्ष गणित की विभिन्न शाखाओं और अनुप्रयुक्त क्षेत्रों दोनों में महत्वपूर्ण भूमिका निभाते हैं, विशेष रूप से रैखिक प्रोग्रामिंग में।
+उत्तल बहुशीर्ष गणित की विभिन्न शाखाओं और अनुप्रयुक्त क्षेत्रों दोनों में महत्वपूर्ण भूमिका निभाते हैं, विशेष रूप से रैखिक प्रोग्रामिंग में इसकी विशेष भूमिका होती हैं।
-ग्रुनबाम की प्रभावशाली पाठ्यपुस्तकों में<ref name=grun/>और ज़िग्लर<ref name=zieg/>विषय पर, साथ ही असतत ज्यामिति में कई अन्य ग्रंथों में, उत्तल पॉलीटोप्स को अक्सर पॉलीटोप्स कहा जाता है। ग्रुनबाउम बताते हैं कि यह केवल उत्तल शब्द की अंतहीन पुनरावृत्ति से बचने के लिए है, और यह कि चर्चा को केवल उत्तल विविधता (पृष्ठ 51) पर लागू करने के रूप में समझा जाना चाहिए।
+इस प्रकार ग्रुनबाम की प्रभावशाली पाठ्यपुस्तकों में<ref name=grun/>और ज़िग्लर<ref name=zieg/> विषय पर साथ ही असतत ज्यामिति में कई अन्य ग्रंथों में, उत्तल पॉलीटोप्स को अधिकांशतः पॉलीटोप्स कहा जाता है। इस कारण ग्रुनबाउम बताते हैं कि यह केवल उत्तल शब्द की अंतहीन पुनरावृत्ति से बचने के लिए करते हैं, और यह कि चर्चा को केवल उत्तल विविधता (पृष्ठ 51) पर लागू करने के रूप में समझा जाना चाहिए।
-एक पॉलीटॉप को पूर्ण-आयामी कहा जाता है यदि यह है <math>n</math>-आयामी वस्तु में <math>\mathbb{R}^n</math>.
+एक पॉलीटॉप को पूर्ण-आयामी कहा जाता है, इस कारण यदि यह <math>n</math>-आयामी वस्तु में <math>\mathbb{R}^n</math> के रूप में प्रदर्शित होता हैं।
 == उदाहरण ==
 *बाध्य उत्तल पॉलीटोप्स के कई उदाहरण लेख पॉलीहेड्रॉन में पाए जा सकते हैं।
-*2-आयामी मामले में पूर्ण-आयामी उदाहरण आधा-विमान, दो समानांतर रेखाओं के बीच पट्टी, कोण आकार (दो गैर-समानांतर अर्ध-विमानों का प्रतिच्छेदन), उत्तल बहुभुज श्रृंखला द्वारा परिभाषित आकृति है इसके सिरों से जुड़ी दो किरणें (ज्यामिति) और उत्तल बहुभुज।
+*2-आयामी मामले में पूर्ण-आयामी उदाहरण आधा-विमान, दो समानांतर रेखाओं के बीच पट्टी, कोण आकार (दो गैर-समानांतर अर्ध-विमानों का प्रतिच्छेदन), उत्तल बहुभुज श्रृंखला द्वारा परिभाषित आकृति है इसके सिरों से जुड़ी दो किरणें (ज्यामिति) और उत्तल बहुभुज माना जाता हैं।
-*एक असीमित उत्तल पॉलीटोप के विशेष मामले दो समानांतर हाइपरप्लेन के बीच स्लैब (ज्यामिति), दो गैर-समानांतर हाफ-स्पेस (ज्यामिति) द्वारा परिभाषित वेज हैं। हाफ-स्पेस, पॉलीहेड्रल सिलेंडर (अनंत प्रिज्म (ज्यामिति)), और बहुफलकीय शंकु (अनंत शंकु) सामान्य बिंदु से गुजरने वाली तीन या अधिक अर्ध-रिक्तियों द्वारा परिभाषित।
+*किसी असीमित उत्तल पॉलीटोप के विशेष स्थितियों को दो समानांतर हाइपरप्लेन के बीच स्लैब (ज्यामिति), दो गैर-समानांतर हाफ-स्पेस (ज्यामिति) द्वारा परिभाषित वेज हैं। इस प्रकार हाफ-स्पेस, पॉलीहेड्रल सिलेंडर (अनंत प्रिज्म (ज्यामिति)), और बहुफलकीय शंकु (अनंत शंकु) सामान्य बिंदु से गुजरने वाली तीन या अधिक अर्ध-रिक्तियों द्वारा परिभाषित किया जाता हैं।
 == परिभाषाएँ ==
-हाथ में समस्या के लिए अधिक उपयुक्त क्या है, इस पर निर्भर करते हुए उत्तल पॉलीटॉप को कई तरीकों से परिभाषित किया जा सकता है। ग्रुनबाम की परिभाषा अंतरिक्ष में बिंदुओं के उत्तल सेट के संदर्भ में है। अन्य महत्वपूर्ण परिभाषाएँ हैं: अर्ध-स्थान (ज्यामिति) के प्रतिच्छेदन (सेट सिद्धांत) के रूप में | अर्ध-स्थान (आधा-स्थान प्रतिनिधित्व) और बिंदुओं के सेट के उत्तल पतवार के रूप में (शीर्ष प्रतिनिधित्व)।
+इस समस्या के लिए अधिक उपयुक्त क्या है, इस पर निर्भर करते हुए उत्तल पॉलीटॉप को कई विधियों से परिभाषित किया जा सकता है। इस प्रकार ग्रुनबाम की परिभाषा अंतरिक्ष में बिंदुओं के उत्तल समुच्चय के संदर्भ में है। अन्य महत्वपूर्ण परिभाषाएँ हैं: अर्ध-स्थान (ज्यामिति) के प्रतिच्छेदन (समुच्चय सिद्धांत) के रूप में या अर्ध-स्थान (आधा-स्थान प्रतिनिधित्व) और बिंदुओं के समुच्चय के उत्तल आवरण के रूप में (शीर्ष प्रतिनिधित्व) किया जाता हैं।
-=== वर्टेक्स प्रतिनिधित्व (उत्तल पतवार) ===
+=== अक्षीय प्रतिनिधित्व (उत्तल आवरण) ===
-अपनी पुस्तक उत्तल पॉलीटोप्स में, ग्रुनबाम उत्तल पॉलीटॉप को 'कॉम्पैक्ट स्पेस उत्तल सेट के साथ चरम बिंदुओं की सीमित संख्या' के रूप में परिभाषित करता है:
+अपनी पुस्तक उत्तल पॉलीटोप्स में, ग्रुनबाम उत्तल पॉलीटॉप को 'कॉम्पैक्ट स्पेस उत्तल समुच्चय के साथ उच्च बिंदुओं की सीमित संख्या' के रूप में परिभाषित करता है:
-: एक सेट <math>K</math> का <math>\mathbb{R}^n</math> उत्तल है अगर, अलग-अलग बिंदुओं की प्रत्येक जोड़ी के लिए <math>a</math>, <math>b</math> में <math>K</math>, समापन बिंदु के साथ बंद खंड <math>a</math> तथा <math>b</math> के भीतर निहित है <math>K</math>.
+: एक समुच्चय <math>K</math> का <math>\mathbb{R}^n</math> उत्तल है यदि, अलग-अलग बिंदुओं की प्रत्येक जोड़ी के लिए <math>a</math>, <math>b</math> में <math>K</math>, समापन बिंदु के साथ बंद खंड <math>a</math> तथा <math>b</math> के भीतर <math>K</math> निहित रहता है।
-यह परिमित उत्तल पॉलीटॉप को बिंदुओं के परिमित सेट के उत्तल पतवार के रूप में परिभाषित करने के बराबर है, जहां परिमित सेट में पॉलीटॉप के चरम बिंदुओं का सेट होना चाहिए। इस तरह की परिभाषा को शीर्ष प्रतिनिधित्व (वी-प्रतिनिधित्व या वी-विवरण) कहा जाता है।<ref name=grun/> कॉम्पैक्ट उत्तल पॉलीटॉप के लिए, न्यूनतम वी-विवरण अद्वितीय है और यह पॉलीटॉप के वर्टेक्स (ज्यामिति) के सेट द्वारा दिया गया है।<ref name=grun/>एक उत्तल पॉलीटॉप को [[अभिन्न पॉलीटॉप]] कहा जाता है यदि इसके सभी कोने पूर्णांक निर्देशांक होते हैं।
+यह परिमित उत्तल पॉलीटॉप को बिंदुओं के परिमित समुच्चय के उत्तल आवरण के रूप में परिभाषित करने के समान है, जहां परिमित समुच्चय में पॉलीटॉप के उच्च बिंदुओं का समुच्चय होना चाहिए। इस प्रकार की परिभाषा को शीर्ष प्रतिनिधित्व (वी-प्रतिनिधित्व या वी-विवरण) कहा जाता है।<ref name=grun/> इस कारण कॉम्पैक्ट उत्तल पॉलीटॉप के लिए, न्यूनतम वी-विवरण अद्वितीय है और यह पॉलीटॉप के अक्षीय (ज्यामिति) के समुच्चय द्वारा दिया गया है।<ref name=grun/> इस प्रकार उत्तल पॉलीटॉप को [[अभिन्न पॉलीटॉप]] कहा जाता है यदि इसके सभी कोने पूर्णांक निर्देशांक होते हैं।
-===आधी जगहों का चौराहा===
+===अर्धस्थानों का अंतःखण्ड===
-एक उत्तल पॉलीटॉप को अर्ध-स्थानों की परिमित संख्या के प्रतिच्छेदन के रूप में परिभाषित किया जा सकता है। ऐसी परिभाषा को आधा स्थान प्रतिनिधित्व (एच-प्रतिनिधित्व या एच-विवरण) कहा जाता है।<ref name=grun/> उत्तल पॉलीटॉप के असीम रूप से कई एच-विवरण मौजूद हैं। हालांकि, पूर्ण-आयामी उत्तल पॉलीटॉप के लिए, न्यूनतम एच-विवरण वास्तव में अद्वितीय है और यह पहलू (ज्यामिति) के सेट द्वारा दिया जाता है - हाफस्पेस को परिभाषित करता है।<ref name=grun/>
+एक उत्तल पॉलीटॉप को अर्ध-स्थानों की परिमित संख्या के प्रतिच्छेदन के रूप में परिभाषित किया जा सकता है। ऐसी परिभाषा को आधा स्थान प्रतिनिधित्व (एच-प्रतिनिधित्व या एच-विवरण) कहा जाता है।<ref name=grun/> इस प्रकार उत्तल पॉलीटॉप के उच्चतम रूप से कई एच-विवरण सम्मिलित हैं। चूंकि पूर्ण-आयामी उत्तल पॉलीटॉप के लिए, न्यूनतम एच-विवरण वास्तव में अद्वितीय है और यह पहलू (ज्यामिति) के समुच्चय द्वारा दिया जाता है - हाफस्पेस को परिभाषित करता है।<ref name=grun/>
-एक बंद अर्ध-स्थान को रैखिक असमानता के रूप में लिखा जा सकता है:<ref name=grun>[[Branko Grünbaum]], ''[[Convex Polytopes]]'', 2nd edition, prepared by [[Volker Kaibel]], [[Victor Klee]], and [[Günter M. Ziegler]], 2003, {{ISBN|0-387-40409-0}}, {{ISBN|978-0-387-40409-7}}, 466pp.</ref>
+किसी बंद अर्ध-स्थान को रैखिक असमानता के रूप में लिखा जा सकता है:<ref name=grun>[[Branko Grünbaum]], ''[[Convex Polytopes]]'', 2nd edition, prepared by [[Volker Kaibel]], [[Victor Klee]], and [[Günter M. Ziegler]], 2003, {{ISBN|0-387-40409-0}}, {{ISBN|978-0-387-40409-7}}, 466pp.</ref>
 :<math>a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b</math>
-कहाँ पे <math>n</math> विचाराधीन पॉलीटॉप वाले स्थान का आयाम है। इसलिए, बंद उत्तल पॉलीटॉप को रैखिक असमानताओं की प्रणाली के समाधान के सेट के रूप में माना जा सकता है:
+जहाँ पर <math>n</math> विचाराधीन पॉलीटॉप वाले स्थान का आयाम है। इसलिए, बंद उत्तल पॉलीटॉप को रैखिक असमानताओं की प्रणाली के समाधान के समुच्चय के रूप में माना जा सकता है:
 :<math>\begin{alignat}{7}
@@ Line 47: / Line 47: @@
 a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; \leq \;&&& b_m      \\
 \end{alignat}</math>
-कहाँ पे <math>m</math> पॉलीटॉप को परिभाषित करने वाले आधे-स्थानों की संख्या है। इसे संक्षेप में मैट्रिक्स (गणित) असमानता के रूप में लिखा जा सकता है:
+जहाँ पर <math>m</math> पॉलीटॉप को परिभाषित करने वाले आधे-स्थानों की संख्या है। इसे संक्षेप में आव्यूह (गणित) असमानता के रूप में लिखा जा सकता है:
 :<math>Ax \leq b</math>
-कहाँ पे <math>A</math> <math>m\times n</math> आव्यूह, <math>x</math> <math>n\times1</math> स्तंभ सदिश जिसके निर्देशांक चर हैं <math>x_1</math> प्रति <math>x_n</math>, तथा <math>b</math> <math>m\times1</math> कॉलम वेक्टर जिसका निर्देशांक दाहिनी ओर है <math>b_1</math> प्रति <math>b_m</math> अदिश असमानताओं की।
+जहाँ पर <math>A</math> <math>m\times n</math> आव्यूह, <math>x</math> <math>n\times1</math> स्तंभ सदिश जिसके निर्देशांक चर हैं, इस कारण <math>x_1</math> प्रति <math>x_n</math>, तथा <math>b</math> <math>m\times1</math> कॉलम वेक्टर हैं जिसका निर्देशांक दाहिनी ओर <math>b_1</math> प्रति <math>b_m</math> अदिश असमानताओं की है ।
-एक खुले उत्तल पॉलीटोप को उसी तरह परिभाषित किया गया है, जिसमें गैर-सख्त लोगों के बजाय सूत्रों में सख्त असमानताओं का उपयोग किया गया है।
+एक ओपेन उत्तल पॉलीटोप को उसी तरह परिभाषित किया गया है, जिसमें गैर-सख्त लोगों के अतिरिक्त सूत्रों में सख्त असमानताओं का उपयोग किया गया है।
-की प्रत्येक पंक्ति के गुणांक <math>A</math> तथा <math>b</math> संबंधित अर्ध-स्थान को परिभाषित करने वाली रैखिक असमानता के गुणांक के अनुरूप है। इसलिए, मैट्रिक्स में प्रत्येक पंक्ति पॉलीटॉप के सहायक हाइपरप्लेन से मेल खाती है, हाइपरप्लेन आधे स्थान को बांधता है जिसमें पॉलीटॉप होता है। यदि सहायक हाइपरप्लेन भी पॉलीटॉप को काटता है, तो इसे बाउंडिंग हाइपरप्लेन कहा जाता है (चूंकि यह सहायक हाइपरप्लेन है, यह केवल पॉलीटॉप की सीमा पर पॉलीटोप को काट सकता है)।
+जिसकी प्रत्येक पंक्ति के गुणांक <math>A</math> तथा <math>b</math> संबंधित अर्ध-स्थान को परिभाषित करने वाली रैखिक असमानता के गुणांक के अनुरूप है। इसलिए आव्यूह में प्रत्येक पंक्ति पॉलीटॉप के सहायक हाइपरप्लेन से मेल खाती है, हाइपरप्लेन आधे स्थान को बांधता है जिसमें पॉलीटॉप होता है। यदि सहायक हाइपरप्लेन भी पॉलीटॉप को काटता है, तो इसे बाउंडिंग हाइपरप्लेन कहा जाता है (चूंकि यह सहायक हाइपरप्लेन है, यह केवल पॉलीटॉप की सीमा पर पॉलीटोप को काट सकता है)।
-पूर्वगामी परिभाषा मानती है कि पॉलीटॉप पूर्ण-आयामी है। इस मामले में, असमानताओं को परिभाषित करने का 'अद्वितीय' न्यूनतम सेट है (एक सकारात्मक संख्या से गुणा तक)। इस अनूठी न्यूनतम प्रणाली से संबंधित असमानताओं को आवश्यक कहा जाता है। पॉलीटोप के बिंदुओं का समूह जो समानता के साथ आवश्यक असमानता को संतुष्ट करता है, पहलू कहलाता है।
+पूर्वगामी परिभाषा मानती है कि पॉलीटॉप पूर्ण-आयामी है। इस मामले में, असमानताओं को परिभाषित करने का 'अद्वितीय' न्यूनतम समुच्चय है (एक सकारात्मक संख्या से गुणा तक)। इस अनूठी न्यूनतम प्रणाली से संबंधित असमानताओं को आवश्यक कहा जाता है। पॉलीटोप के बिंदुओं का समूह जो समानता के साथ आवश्यक असमानता को संतुष्ट करता है, पहलू कहलाता है।
-यदि पॉलीटॉप पूर्ण-आयामी नहीं है, तो समाधान <math>Ax\leq b</math> के उचित संबंध उप-स्थान में झूठ बोलना <math>\mathbb{R}^n</math> और इस उप-स्थान में वस्तु के रूप में पॉलीटॉप का अध्ययन किया जा सकता है। इस मामले में, वहाँ रैखिक समीकरण मौजूद हैं जो पॉलीटॉप के सभी बिंदुओं से संतुष्ट हैं। इन समीकरणों में से किसी को परिभाषित असमानताओं में जोड़ने से पॉलीटॉप नहीं बदलता है। इसलिए, सामान्य तौर पर पॉलीटोप को परिभाषित करने वाली असमानताओं का कोई अनूठा न्यूनतम सेट नहीं है।
+यदि पॉलीटॉप पूर्ण-आयामी नहीं है, तो समाधान <math>Ax\leq b</math> के उचित संबंध उप-स्थान में झूठ बोलना <math>\mathbb{R}^n</math> और इस उप-स्थान में वस्तु के रूप में पॉलीटॉप का अध्ययन किया जा सकता है। इस मामले में, वहाँ रैखिक समीकरण सम्मिलित हैं जो पॉलीटॉप के सभी बिंदुओं से संतुष्ट हैं। इस प्रकार इन समीकरणों में से किसी को परिभाषित असमानताओं में जोड़ने से पॉलीटॉप नहीं बदलता है। इसलिए, सामान्य तौर पर पॉलीटोप को परिभाषित करने वाली असमानताओं का कोई अनूठा न्यूनतम समुच्चय नहीं है।
-आम तौर पर मनमाना अर्ध-स्थानों के चौराहे को बाध्य करने की आवश्यकता नहीं होती है। हालांकि अगर कोई उत्तल हल के बराबर परिभाषा चाहता है, तो बाध्यता स्पष्ट रूप से आवश्यक होनी चाहिए।
+आम तौर पर मनमाना अर्ध-स्थानों के अंतःखण्ड को बाध्य करने की आवश्यकता नहीं होती है। चूंकि यदि कोई उत्तल हल के बराबर परिभाषा चाहता है, तो बाध्यता को स्पष्ट रूप से आवश्यक होनी चाहिए।
-=== विभिन्न अभ्यावेदन === का उपयोग करना
+==== विभिन्न अभ्यावेदन का उपयोग करना ====
-दो अभ्यावेदन साथ यह तय करने का कुशल तरीका प्रदान करते हैं कि क्या दिए गए वेक्टर को दिए गए उत्तल पॉलीटॉप में शामिल किया गया है: यह दिखाने के लिए कि यह पॉलीटॉप में है, यह पॉलीटोप वर्टिस (वी-विवरण) के उत्तल संयोजन के रूप में प्रस्तुत करने के लिए पर्याप्त है प्रयोग किया जाता है); यह दिखाने के लिए कि यह पॉलीटॉप में नहीं है, यह एकल परिभाषित असमानता को प्रस्तुत करने के लिए पर्याप्त है जिसका यह उल्लंघन करता है।<ref name="lp">{{Cite Lovasz Plummer}}</ref>{{Rp|256}}
+दो अभ्यावेदन साथ यह तय करने का कुशल विधि प्रदान करते हैं कि क्या दिए गए वेक्टर को दिए गए उत्तल पॉलीटॉप में सम्मिलित किया गया है: यह दिखाने के लिए कि यह पॉलीटॉप में है, यह पॉलीटोप वर्टिस (वी-विवरण) के उत्तल संयोजन के रूप में प्रस्तुत करने के लिए पर्याप्त है प्रयोग किया जाता है); यह दिखाने के लिए कि यह पॉलीटॉप में नहीं है, यह एकल परिभाषित असमानता को प्रस्तुत करने के लिए पर्याप्त है जिसका यह उल्लंघन करता है।<ref name="lp">{{Cite Lovasz Plummer}}</ref>{{Rp|256}}
-सदिशों द्वारा प्रतिनिधित्व में सूक्ष्म बिंदु यह है कि सदिशों की संख्या आयाम में घातीय हो सकती है, इसलिए प्रमाण है कि सदिश पॉलीटॉप में है, वह घातीय रूप से लंबा हो सकता है। सौभाग्य से, कैराथियोडोरी का प्रमेय (उत्तल हल) | कैराथियोडोरी का प्रमेय गारंटी देता है कि पॉलीटॉप में प्रत्येक वेक्टर को अधिकतम डी+1 परिभाषित वैक्टर द्वारा दर्शाया जा सकता है, जहां डी अंतरिक्ष का आयाम है।
+सदिशों द्वारा प्रतिनिधित्व में सूक्ष्म बिंदु यह है कि सदिशों की संख्या आयाम में घातीय हो सकती है, इसलिए प्रमाण है कि सदिश पॉलीटॉप में है, वह घातीय रूप से लंबा हो सकता है। सौभाग्य से, कैराथियोडोरी का प्रमेय (उत्तल हल) | कैराथियोडोरी का प्रमेय गारंटी देता है कि पॉलीटॉप में प्रत्येक वेक्टर को अधिकतम d+1 परिभाषित वैक्टर द्वारा दर्शाया जा सकता है, जहां d अंतरिक्ष का आयाम है।
 === असीमित पॉलीटोप्स का प्रतिनिधित्व ===
-एक असीमित पॉलीटॉप (कभी-कभी कहा जाता है: पॉलीहेड्रॉन) के लिए, एच-विवरण अभी भी मान्य है, लेकिन वी-विवरण को बढ़ाया जाना चाहिए। थिओडोर मोट्ज़किन (1936) ने साबित किया कि किसी भी असीमित पॉलीटोप को बंधे हुए पॉलीटोप और उत्तल शंकु के योग के रूप में दर्शाया जा सकता है।<ref>{{Cite book|last=Motzkin|first=Theodore|title=रैखिक असमानताओं के सिद्धांत में योगदान (पीएचडी शोध प्रबंध)|year=1936|location=Jerusalem}}</ref> दूसरे शब्दों में, असंबद्ध पॉलीटोप में प्रत्येक सदिश अपने शीर्षों (इसके परिभाषित बिंदु) का उत्तल योग है, साथ ही इसके अनंत किनारों (इसकी परिभाषित किरणें) के यूक्लिडियन सदिशों का शंक्वाकार योग है। इसे परिमित आधार प्रमेय कहा जाता है।<ref name="Jeter" />
+एक असीमित पॉलीटॉप (कभी-कभी कहा जाता है: पॉलीहेड्रॉन) के लिए, एच-विवरण अभी भी मान्य है, लेकिन वी-विवरण को बढ़ाया जाना चाहिए। इस प्रकार थिओडोर मोट्ज़किन (1936) ने प्रमाणित किया कि किसी भी असीमित पॉलीटोप को बंधे हुए पॉलीटोप और उत्तल शंकु के योग के रूप में दर्शाया जा सकता है।<ref>{{Cite book|last=Motzkin|first=Theodore|title=रैखिक असमानताओं के सिद्धांत में योगदान (पीएचडी शोध प्रबंध)|year=1936|location=Jerusalem}}</ref> इसी प्रकार दूसरे शब्दों में, असंबद्ध पॉलीटोप में प्रत्येक सदिश अपने शीर्षों (इसके परिभाषित बिंदु) का उत्तल योग है, साथ ही इसके अनंत किनारों (इसकी परिभाषित किरणें) के यूक्लिडियन सदिशों का शंक्वाकार योग है। इसे परिमित आधार प्रमेय कहा जाता है।<ref name="Jeter" />
+== गुण ==
+प्रत्येक (बाध्य) उत्तल पॉलीटॉप सिंप्लेक्स की प्रतिबिंब है, क्योंकि प्रत्येक बिंदु (अंततः कई) शीर्षों का उत्तल संयोजन है। चूंकि, पॉलीटॉप सामान्य रूप से सरलताओं के लिए आइसोमोर्फिक नहीं हैं। यह वेक्टर रिक्त स्थान और रैखिक संयोजन की स्थिति के विपरीत है, प्रत्येक परिमित-आयामी वेक्टर स्थान न केवल प्रतिबिंब को प्रदर्शित करता हैं, यद्दपि वास्तव में यह आइसोमोर्फिक रहता है, इस कारण कुछ आयाम के यूक्लिडियन स्थान (या अन्य क्षेत्रों पर nालॉग) अवस्था में रहते हैं।
+=== फेस लैटिस ===
+{{main|संदर्भित पाॅलीटोप}}
-== गुण ==
+एक उत्तल पॉलीटॉप का फेस (ज्यामिति) आधा स्थान (ज्यामिति) के साथ पॉलीटॉप का कोई अंतःखण्ड है, जैसे कि पॉलीटॉप के आंतरिक बिंदुओं में से कोई भी आधे स्थान की सीमा पर नहीं है। इस कारण समतुल्य रूप से, फेस पॉलीटॉप की कुछ वैध असमानता में समानता देने वाले बिंदुओं का समूह है।<ref name="lp" />{{Rp|258}}
-प्रत्येक (बाध्य) उत्तल पॉलीटॉप सिंप्लेक्स की छवि है, क्योंकि प्रत्येक बिंदु (अंततः कई) शीर्षों का उत्तल संयोजन है। हालांकि, पॉलीटॉप सामान्य रूप से सरलताओं के लिए आइसोमोर्फिक नहीं हैं। यह वेक्टर रिक्त स्थान और रैखिक संयोजन के मामले के विपरीत है, प्रत्येक परिमित-आयामी वेक्टर स्थान न केवल छवि है, बल्कि वास्तव में आइसोमोर्फिक है, कुछ आयाम के यूक्लिडियन स्थान (या अन्य क्षेत्रों पर एनालॉग)।
-=== चेहरा जाली ===
+यदि पॉलीटोप डी-आयामी है, तो इसके पहलू (गणित) इसके (d − 1)-आयामी फेस हैं, इसके शीर्ष (ज्यामिति) इसके 0-आयामी फेस हैं, इसके किनारे (ज्यामिति) इसके 1-आयामी फेस हैं, और इसके कटक (ज्यामिति) इसके (d − 2)-विमीय फलक हैं।
-{{main|abstract polytope}}
-एक उत्तल पॉलीटॉप का चेहरा (ज्यामिति) आधा स्थान (ज्यामिति) के साथ पॉलीटॉप का कोई चौराहे है, जैसे कि पॉलीटॉप के आंतरिक बिंदुओं में से कोई भी आधे स्थान की सीमा पर नहीं है। समतुल्य रूप से, चेहरा पॉलीटॉप की कुछ वैध असमानता में समानता देने वाले बिंदुओं का समूह है।<ref name="lp" />{{Rp|258}}
-यदि पॉलीटोप डी-आयामी है, तो इसके पहलू (गणित) इसके (डी − 1)-आयामी चेहरे हैं, इसके शीर्ष (ज्यामिति) इसके 0-आयामी चेहरे हैं, इसके किनारे (ज्यामिति) इसके 1-आयामी चेहरे हैं, और इसके कटक (ज्यामिति) इसके (d − 2)-विमीय फलक हैं।
-मैट्रिक्स असमानता द्वारा परिभाषित उत्तल पॉलीटॉप पी दिया गया <math>Ax \leq b</math>, यदि A में प्रत्येक पंक्ति बाउंडिंग हाइपरप्लेन से मेल खाती है और अन्य पंक्तियों से रैखिक रूप से स्वतंत्र है, तो P का प्रत्येक पहलू A की ठीक पंक्ति से मेल खाता है, और इसके विपरीत। किसी दिए गए पहलू पर प्रत्येक बिंदु मैट्रिक्स में संबंधित पंक्ति की रैखिक समानता को संतुष्ट करेगा। (यह अन्य पंक्तियों में समानता को संतुष्ट कर भी सकता है और नहीं भी)। इसी प्रकार, रिज पर प्रत्येक बिंदु ए की दो पंक्तियों में समानता को पूरा करेगा।
+आव्यूह असमानता द्वारा परिभाषित उत्तल पॉलीटॉप पी <math>Ax \leq b</math> दिया गया है, यदि A में प्रत्येक पंक्ति बाउंडिंग हाइपरप्लेन से मेल खाती है और अन्य पंक्तियों से रैखिक रूप से स्वतंत्र है, तो P का प्रत्येक पहलू A की ठीक पंक्ति से मेल खाता है, और इसके विपरीत किसी दिए गए पहलू पर प्रत्येक बिंदु आव्यूह में संबंधित पंक्ति की रैखिक समानता को संतुष्ट करता हैं। (यह अन्य पंक्तियों में समानता को संतुष्ट कर भी सकता है और नहीं भी) को इसी प्रकार, रिज पर प्रत्येक बिंदु ए की दो पंक्तियों में समानता को पूरा करता हैं।
-[[File:Pyramid face lattice.svg|thumb|360px|एक हस आरेख के रूप में तैयार वर्ग पिरामिड का चेहरा जाली; जाली में प्रत्येक चेहरे को उसके शीर्ष सेट द्वारा लेबल किया जाता है।]]सामान्य तौर पर, (एन − जे)-आयामी चेहरा ए की जे विशिष्ट पंक्तियों में समानता को संतुष्ट करता है। ये पंक्तियाँ चेहरे का 'आधार' बनाती हैं। ज्यामितीय रूप से बोलना, इसका मतलब है कि चेहरा पॉलीटोप पर बिंदुओं का समूह है जो पॉलीटोप के बाउंडिंग हाइपरप्लेन के जे के चौराहे पर स्थित है।
+[[File:Pyramid face lattice.svg|thumb|360px|एक हस आरेख के रूप में तैयार वर्ग पिरामिड का फेस नेट; नेट में प्रत्येक फेस को उसके शीर्ष समुच्चय द्वारा लेबल किया जाता है।]]सामान्य तौर पर, (n − जे)-आयामी फेस ए की जे विशिष्ट पंक्तियों में समानता को संतुष्ट करता है। इस प्रकार ये पंक्तियाँ फेस का 'आधार' बनाती हैं। ज्यामितीय रूप से बोलना, इसका अर्थ है कि फेस पॉलीटोप पर बिंदुओं का समूह है जो पॉलीटोप के बाउंडिंग हाइपरप्लेन के जे के अंतःखण्ड पर स्थित है।
-एक उत्तल पॉलीटॉप के चेहरे इस प्रकार यूलेरियन पोसेट जाली (ऑर्डर) बनाते हैं, जिसे इसका 'फेस लैटिस' कहा जाता है, जहां आंशिक क्रम चेहरों के सेट द्वारा होता है। ऊपर दिए गए चेहरे की परिभाषा पॉलीटॉप और खाली सेट दोनों को चेहरे के रूप में माना जाता है, यह सुनिश्चित करता है कि चेहरे की प्रत्येक जोड़ी में शामिल हो और चेहरे की जाली में मिल जाए। संपूर्ण पॉलीटॉप जाली का अद्वितीय अधिकतम तत्व है, और खाली सेट, जिसे प्रत्येक पॉलीटॉप का (-1) -डायमेंशनल फेस (एक 'नल पॉलीटोप') माना जाता है, जाली का अद्वितीय न्यूनतम तत्व है।
+एक उत्तल पॉलीटॉप के फेस इस प्रकार यूलेरियन पोसमुच्चय नेट (ऑर्डर) बनाते हैं, जिसे इसका 'फेस लैटिस' कहा जाता है, जहां आंशिक क्रम फेस के समुच्चय द्वारा होता है। इस कारण ऊपर दिए गए फेस की परिभाषा पॉलीटॉप और रिक्त समुच्चय दोनों को फेस के रूप में माना जाता है, यह सुनिश्चित करता है कि फेस की प्रत्येक जोड़ी में सम्मिलित हो और फेस की नेट में मिल जाती हैं। इस प्रकार संपूर्ण पॉलीटॉप नेट का अद्वितीय अधिकतम तत्व है, और रिक्त समुच्चय, जिसे प्रत्येक पॉलीटॉप का (-1) -डायमेंशनल फेस (एक 'नल पॉलीटोप') माना जाता है, नेट का अद्वितीय न्यूनतम तत्व है।
-दो पॉलीटोप्स को 'कॉम्बिनेटरियल आइसोमोर्फिक' कहा जाता है यदि उनके चेहरे की जाली आइसोमोर्फिज्म हैं।
+दो पॉलीटोप्स को 'कॉम्बिनेटरियल आइसोमोर्फिक' कहा जाता है यदि उनके फेस की नेट आइसोमोर्फिज्म हैं।
-'पॉलीटॉप ग्राफ' ('पॉलीटोपल ग्राफ', 'पॉलीटॉप का ग्राफ', '1-कंकाल') केवल पॉलीटॉप के कोने और किनारों का सेट है, जो उच्च-आयामी चेहरों की अनदेखी करता है। उदाहरण के लिए, पॉलीहेड्रल ग्राफ त्रि-आयामी पॉलीटॉप का पॉलीटॉप ग्राफ है। हस्लर व्हिटनी के परिणामस्वरूप<ref>{{cite journal |author-link=Hassler Whitney |first=Hassler |last=Whitney |title=सर्वांगसम रेखांकन और रेखांकन की कनेक्टिविटी|journal=Amer. J. Math. |volume=54 |issue=1 |pages=150–168 |year=1932 |jstor=2371086 |doi=10.2307/2371086|hdl=10338.dmlcz/101067 |hdl-access=free }}</ref> त्रि-आयामी पॉलीटॉप का चेहरा जाली इसके ग्राफ द्वारा निर्धारित किया जाता है। मनमाना आयाम के सरल पॉलीटोप्स के लिए भी यही सच है (ब्लाइंड एंड मणि-लेवित्स्का 1987, मीका पर्ल्स का अनुमान साबित करना)।<ref>{{citation
+'पॉलीटॉप ग्राफ' ('पॉलीटोपल ग्राफ', 'पॉलीटॉप का ग्राफ', '1-संरचना') केवल पॉलीटॉप के कोने और किनारों का समुच्चय है, जो उच्च-आयामी फेस की अनदेखी करता है। उदाहरण के लिए, पॉलीहेड्रल ग्राफ त्रि-आयामी पॉलीटॉप का पॉलीटॉप ग्राफ है। हस्लर व्हिटनी के परिणामस्वरूप<ref>{{cite journal |author-link=Hassler Whitney |first=Hassler |last=Whitney |title=सर्वांगसम रेखांकन और रेखांकन की कनेक्टिविटी|journal=Amer. J. Math. |volume=54 |issue=1 |pages=150–168 |year=1932 |jstor=2371086 |doi=10.2307/2371086|hdl=10338.dmlcz/101067 |hdl-access=free }}</ref> त्रि-आयामी पॉलीटॉप का फेस नेट इसके ग्राफ द्वारा निर्धारित किया जाता है। इस प्रकार इसके अनुरूप स्वंय इस आयाम के सरल पॉलीटोप्स के लिए भी यही सच है (ब्लाइंड एंड मणि-लेवित्स्का 1987, मीका पर्ल्स का अनुमान प्रमाणित करना) हैं।<ref>{{citation
   | last1 = Blind | first1 = Roswitha | author1-link = Roswitha Blind
   | last2 = Mani-Levitska | first2 = Peter
@@ Line 107: / Line 108: @@
   | volume = 49
   | year = 1988| doi-access = free
-  }}.</ref> अद्वितीय सिंक ओरिएंटेशन के आधार पर सरल प्रमाण देता है। क्योंकि इन पॉलीटॉप्स के चेहरे की जाली उनके ग्राफ़ द्वारा निर्धारित की जाती है, यह तय करने की समस्या है कि क्या दो त्रि-आयामी या सरल उत्तल पॉलीटोप्स कॉम्बीनेटरियल आइसोमोर्फिक हैं, ग्राफ़ आइसोमोर्फिज़्म समस्या के विशेष मामले के रूप में समान रूप से तैयार किए जा सकते हैं। हालांकि, इन समस्याओं को विपरीत दिशा में अनुवाद करना भी संभव है, यह दर्शाता है कि पोलीटॉप समरूपता परीक्षण ग्राफ-समरूपता पूर्ण है।<ref>{{cite journal |first=Volker |last=Kaibel |first2=Alexander |last2=Schwartz |url=http://eprintweb.org/S/authors/All/ka/Kaibel/16 |title=पॉलीटॉप आइसोमोर्फिज्म समस्याओं की जटिलता पर|journal=[[Graphs and Combinatorics]] |volume=19 |issue=2 |pages=215–230 |year=2003 |arxiv=math/0106093 |doi=10.1007/s00373-002-0503-y |url-status=dead |archive-url=https://web.archive.org/web/20150721175904/http://eprintweb.org/S/authors/All/ka/Kaibel/16 |archive-date=2015-07-21 }}</ref>
+  }}.</ref> द्वारा अद्वितीय सिंक ओरिएंटेशन के आधार पर सरल प्रमाण देता है। क्योंकि इन पॉलीटॉप्स के फेस की नेट उनके ग्राफ़ द्वारा निर्धारित की जाती है, यह तय करने की समस्या है कि क्या दो त्रि-आयामी या सरल उत्तल पॉलीटोप्स कॉम्बीनेटरियल आइसोमोर्फिक हैं, इस प्रकार किसी ग्राफ़ को आइसोमोर्फिज़्म समस्या के विशेष स्थिति के रूप में समान रूप से तैयार किए जा सकते हैं। चूंकि, इन समस्याओं को विपरीत दिशा में अनुवाद करना भी संभव है, यह दर्शाता है कि पोलीटॉप समरूपता परीक्षण ग्राफ-समरूपता पूर्ण है।<ref>{{cite journal |first=Volker |last=Kaibel |first2=Alexander |last2=Schwartz |url=http://eprintweb.org/S/authors/All/ka/Kaibel/16 |title=पॉलीटॉप आइसोमोर्फिज्म समस्याओं की जटिलता पर|journal=[[Graphs and Combinatorics]] |volume=19 |issue=2 |pages=215–230 |year=2003 |arxiv=math/0106093 |doi=10.1007/s00373-002-0503-y |url-status=dead |archive-url=https://web.archive.org/web/20150721175904/http://eprintweb.org/S/authors/All/ka/Kaibel/16 |archive-date=2015-07-21 }}</ref>
 === सांस्थितिक गुण ===
-एक उत्तल पॉलीटोप, आर के किसी भी कॉम्पैक्ट उत्तल उपसमुच्चय की तरह<sup>n</sup>, बंद गेंद (गणित) के लिए होमोमोर्फिज्म है।<ref name=bredon>[[Glen Bredon|Glen E. Bredon]], ''Topology and Geometry'', 1993, {{ISBN|0-387-97926-3}}, p. 56.</ref> मान लीजिए m पॉलीटॉप के आयाम को निरूपित करता है। यदि पॉलीटॉप पूर्ण-आयामी है, तो एम = एन। इसलिए उत्तल पॉलीटॉप सीमा के साथ एम-आयामी मैनिफोल्ड (गणित) है, इसकी यूलर विशेषता 1 है, और इसका मौलिक समूह तुच्छ है। उत्तल पॉलीटॉप की सीमा n-sphere|(m − 1)-sphere के लिए होमियोमॉर्फिक है। सम m के लिए बाउंड्री की यूलर विशेषता 0 और विषम m के लिए 2 है। सीमा को (m − 1)-विमीय दीर्घवृत्तीय स्थान के टेसलेशन के रूप में भी माना जा सकता है — यानी गोलाकार खपरैल के रूप में।
+उत्तल पॉलीटोप, R<sup>n</sup> के किसी भी कॉम्पैक्ट उत्तल उपसमुच्चय के समान क्लोज्ड बाॅल (गणित) के लिए होमोमोर्फिज्म है।<ref name=bredon>[[Glen Bredon|Glen E. Bredon]], ''Topology and Geometry'', 1993, {{ISBN|0-387-97926-3}}, p. 56.</ref> मान लीजिए m पॉलीटॉप के आयाम को निरूपित करता है। यदि पॉलीटॉप पूर्ण-आयामी है, तो m = n के समान होता हैं। इसलिए उत्तल पॉलीटॉप सीमा के साथ m-आयामी मैनिफोल्ड (गणित) है, इसकी यूलर विशेषता 1 है, और इसका मौलिक समूह तुच्छ है। इस प्रकार उत्तल पॉलीटॉप की सीमा n-वृत्त या (m − 1)-वृत्त के लिए होमियोमॉर्फिक रूप के समान रहता है। इस प्रकार सम m के लिए बाउंड्री की यूलर विशेषता 0 और विषम m के लिए 2 है। इस कारण इस सीमा को (m − 1)-विमीय दीर्घवृत्तीय स्थान के टेसलेशन के रूप में भी माना जा सकता है — अर्ताथ गोलाकार खपरैल के रूप में उपयोग किया जाता हैं।
 === साधारण अपघटन ===
@@ Line 118: / Line 117: @@
 कुछ गुणों को संतुष्ट करते हुए, उत्तल पॉलीटॉप को साधारण जटिल, या सिंप्लेक्स के संघ में विघटित किया जा सकता है।
-एक उत्तल आर-आयामी पॉलीटॉप पी दिया गया है, इसके शीर्षों का उपसमुच्चय जिसमें (आर+1) आत्मीयता से स्वतंत्र बिंदु होते हैं, सिम्प्लेक्स | आर-सिम्प्लेक्स को परिभाषित करता है। उपसमुच्चय का संग्रह बनाना संभव है जैसे कि संबंधित सरलताओं का संघ पी के बराबर है, और किसी भी दो सरलताओं का चौराहे या तो खाली है या निम्न-आयामी सरल है। यह साधारण अपघटन उत्तल पॉलीटोप की मात्रा की गणना के लिए कई तरीकों का आधार है, क्योंकि सरल सूत्र की मात्रा आसानी से सूत्र द्वारा दी जाती है।<ref>{{Cite book | last1 = Büeler | first1 = B. | last2 = Enge | first2 = A. | last3 = Fukuda | first3 = K. |author3-link=Komei Fukuda| doi = 10.1007/978-3-0348-8438-9_6 | chapter = Exact Volume Computation for Polytopes: A Practical Study | title = पॉलीटोप्स - कॉम्बिनेटरिक्स और कम्प्यूटेशन| pages = 131 | year = 2000 | isbn = 978-3-7643-6351-2 }}</ref>
+एक उत्तल आर-आयामी पॉलीटॉप पी दिया गया है, इसके शीर्षों का उपसमुच्चय जिसमें (आर+1) आत्मीयता से स्वतंत्र बिंदु होते हैं, इस प्रकार सिम्प्लेक्स या आर-सिम्प्लेक्स को परिभाषित करता है। उपसमुच्चय का संग्रह बनाना संभव है जैसे कि संबंधित सरलताओं का संघ पी के बराबर है, और किसी भी दो सरलताओं का अंतःखण्ड या तो रिक्त है या निम्न-आयामी सरल है। इस प्रकार यह साधारण अपघटन उत्तल पॉलीटोप की मात्रा की गणना के लिए कई तरीकों का आधार है, क्योंकि सरल सूत्र की मात्रा आसानी से सूत्र द्वारा दी जाती है।<ref>{{Cite book | last1 = Büeler | first1 = B. | last2 = Enge | first2 = A. | last3 = Fukuda | first3 = K. |author3-link=Komei Fukuda| doi = 10.1007/978-3-0348-8438-9_6 | chapter = Exact Volume Computation for Polytopes: A Practical Study | title = पॉलीटोप्स - कॉम्बिनेटरिक्स और कम्प्यूटेशन| pages = 131 | year = 2000 | isbn = 978-3-7643-6351-2 }}</ref>
-== उत्तल पॉलीटॉप == के लिए एल्गोरिदमिक समस्याएं
+== उत्तल पॉलीटॉप के लिए एल्गोरिदमिक समस्याएं ==
 === अभ्यावेदन का निर्माण ===
-एक उत्तल पॉलीटॉप के विभिन्न अभ्यावेदन में अलग-अलग उपयोगिता होती है, इसलिए प्रतिनिधित्व का निर्माण महत्वपूर्ण समस्या है। वी-प्रतिनिधित्व के निर्माण की समस्या को शीर्ष गणना समस्या के रूप में जाना जाता है और एच-प्रतिनिधित्व के निर्माण की समस्या को पहलू गणना समस्या के रूप में जाना जाता है। जबकि बंधे हुए उत्तल पॉलीटॉप का वर्टेक्स सेट विशिष्ट रूप से इसे परिभाषित करता है, विभिन्न अनुप्रयोगों में पॉलीटोप की संयोजी संरचना के बारे में अधिक जानना महत्वपूर्ण है, अर्थात, इसके चेहरे की जाली के बारे में। विभिन्न उत्तल हल एल्गोरिदम पहलू गणना और चेहरे जाली निर्माण दोनों के साथ सौदा करते हैं।
+उत्तल पॉलीटॉप के विभिन्न अभ्यावेदन में अलग-अलग उपयोगिता होती है, इसलिए प्रतिनिधित्व का निर्माण महत्वपूर्ण समस्या है। इस प्रकार वी-प्रतिनिधित्व के निर्माण की समस्या को शीर्ष गणना समस्या के रूप में जाना जाता है और एच-प्रतिनिधित्व के निर्माण की समस्या को पहलू गणना समस्या के रूप में जाना जाता है। जबकि बंधे हुए उत्तल पॉलीटॉप का अक्षीय समुच्चय विशिष्ट रूप से इसे परिभाषित करता है, विभिन्न अनुप्रयोगों में पॉलीटोप की संयोजी संरचना के बारे में अधिक जानना महत्वपूर्ण है, अर्थात, इसके फेस की नेट के बारे में उपयोग किया जाता हैं। इस प्रकार विभिन्न उत्तल हल एल्गोरिदम पहलू गणना और फेस नेट निर्माण दोनों के साथ संयोजन करते हैं।
-प्लानर मामले में, यानी, उत्तल बहुभुज के लिए, उत्तल पतवार के चारों ओर ऑर्डरिंग वर्टिस (प्रतिक्रिया किनारों) के लिए दोनों पहलू और शीर्ष गणना समस्याएं होती हैं। यह तुच्छ कार्य है जब उत्तल बहुभुज को पारंपरिक तरीके से बहुभुजों के लिए निर्दिष्ट किया जाता है, अर्थात, इसके शीर्षों के क्रमबद्ध क्रम द्वारा <math>v_1,\dots, v_m</math>. जब शीर्षों (या किनारों) की इनपुट सूची अनियंत्रित होती है, तो समस्याओं की समय जटिलता बिग ओह नोटेशन (एम लॉग एम) बन जाती है।<ref>{{Introduction to Algorithms|edition=2|chapter=33.3 Finding the convex hull|pages=947–957}}</ref> संगणना के बीजगणितीय निर्णय ट्री मॉडल में मैचिंग लोअर बाउंड जाना जाता है।<ref>{{citation
+प्लानर स्थिति में, उत्तल बहुभुज के लिए उत्तल आवरण के चारों ओर ऑर्डरिंग अक्ष (प्रतिक्रिया किनारों) के लिए दोनों पहलू और शीर्ष गणना समस्याएं होती हैं। यह तुच्छ कार्य है जब उत्तल बहुभुज को पारंपरिक तरीके से बहुभुजों के लिए निर्दिष्ट किया जाता है, अर्थात इसके शीर्षों के क्रमबद्ध क्रम द्वारा <math>v_1,\dots, v_m</math>. जब शीर्षों (या किनारों) की इनपुट सूची अनियंत्रित होती है, तो समस्याओं की समय जटिलता बिग ओह नोटेशन (m लॉग m) बन जाती है।<ref>{{Introduction to Algorithms|edition=2|chapter=33.3 Finding the convex hull|pages=947–957}}</ref> इस प्रकार संगणना के बीजगणितीय निर्णय ट्री मॉडल में मैचिंग लोअर बाउंड जाना जाता है।<ref>{{citation
   | last = Yao | first = Andrew Chi Chih | author-link = Andrew Yao
   | doi = 10.1145/322276.322289
@@ Line 143: / Line 141: @@
   | title = Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83)
   | year = 1983}}.</ref>
+=== आयतन की गणना ===
+कम्प्यूटेशनल ज्यामिति के क्षेत्र में उत्तल पॉलीटॉप की मात्रा की गणना करने का कार्य अध्ययन किया गया है। इस प्रकार वॉल्यूम की गणना सन्निकटन एल्गोरिथ्म की जा सकती है, उदाहरण के लिए, उत्तल आयतन सन्निकटन विधि का उपयोग करते हुए, जब सदस्यता ऑरेकल मशीन तक पहुँच होती है। इस प्रकार सटीक एल्गोरिदम के लिए यहाँ पर मुख्य बाधा यह है कि, जब रैखिक असमानता की समीकरण प्रणाली के रूप में उत्तल पॉलीटॉप का प्रतिनिधित्व दिया जाता है, तो इस प्रकार पॉलीटॉप की मात्रा में थोड़ी-लंबाई हो सकती है जो इस प्रतिनिधित्व में बहुपद नहीं है।<ref>{{Cite journal|last=Lawrence|first=Jim|date=1991|title=पॉलीटॉप मात्रा गणना|url=https://www.ams.org/mcom/1991-57-195/S0025-5718-1991-1079024-2/|journal=Mathematics of Computation|language=en|volume=57|issue=195|pages=259–271|doi=10.1090/S0025-5718-1991-1079024-2|issn=0025-5718|doi-access=free}}</ref>
-=== वॉल्यूम गणना ===
-कम्प्यूटेशनल ज्यामिति के क्षेत्र में उत्तल पॉलीटॉप की मात्रा की गणना करने का कार्य अध्ययन किया गया है। वॉल्यूम की गणना सन्निकटन एल्गोरिथ्म की जा सकती है, उदाहरण के लिए, उत्तल आयतन सन्निकटन तकनीक का उपयोग करते हुए, जब सदस्यता ऑरेकल मशीन तक पहुँच होती है। सटीक एल्गोरिदम के लिए, बाधा यह है कि, जब रैखिक असमानता की समीकरण प्रणाली के रूप में उत्तल पॉलीटॉप का प्रतिनिधित्व दिया जाता है, तो पॉलीटॉप की मात्रा में थोड़ी-लंबाई हो सकती है जो इस प्रतिनिधित्व में बहुपद नहीं है।<ref>{{Cite journal|last=Lawrence|first=Jim|date=1991|title=पॉलीटॉप मात्रा गणना|url=https://www.ams.org/mcom/1991-57-195/S0025-5718-1991-1079024-2/|journal=Mathematics of Computation|language=en|volume=57|issue=195|pages=259–271|doi=10.1090/S0025-5718-1991-1079024-2|issn=0025-5718|doi-access=free}}</ref>
 == यह भी देखें ==
 * ओरिएंटेड मैट्रोइड

Anonymous

Search

उत्तल पॉलीटॉप: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:12, 9 May 2023

Contents

उदाहरण