बहुभुजीकरण: Difference between revisions

Revision as of 13:12, 4 July 2023

छह बिंदुओं के एक सेट के 16 बहुभुजीकरण

कम्प्यूटेशनल ज्यामिति में, यूक्लिडियन प्लेन में बिंदुओं के एक सीमित समुच्चय का बहुभुजीकरण एक सरल बहुभुज होता है जिसके शीर्ष दिए गए बिंदुओं के साथ होते हैं।^[1] बहुभुजीकरण को बहुभुजकरण,^[2] सरल बहुभुजीकरण,^[3] हैमिल्टनियन बहुभुज,^[4] गैर-क्रॉसिंग हैमिल्टनियन चक्र,^[5] या क्रॉसिंग-फ्री स्ट्रेट-एज स्पैनिंग चक्र भी कहा जा सकता है।^[6]

प्रत्येक बिंदु सेट जो एक रेखा पर स्थित नहीं है, उसमें कम से कम एक बहुभुजीकरण होता है, जिसे बहुपद समय में पाया जा सकता है। उत्तल स्थिति में बिंदुओं के लिए, केवल एक ही होता है, लेकिन कुछ अन्य बिंदु सेटों के लिए, चरघातांकीय रूप से कई हो सकते हैं। कई प्राकृतिक अनुकूलन मानदंडों के तहत एक इष्टतम बहुभुजीकरण ढूंढना एक कठिन समस्या है, जिसमें एक विशेष मामले में ट्रैवलिंग सेल्समैन की समस्या भी शामिल है। सभी बहुभुजीकरणों की गणना की जटिलता अज्ञात बनी हुई है।

परिभाषा

बहुभुजीकरण एक साधारण बहुभुज है जिसमें यूक्लिडियन प्लेन में दिए गए बिंदुओं का समुच्चय होता है। एक बहुभुज को इसके शीर्ष पर एक चक्रीय क्रम द्वारा वर्णित किया जा सकता है, जो बहुभुज के किनारों, पंक्ति खंडों द्वारा लगातार जोड़ों में जुड़ा होता है। एक बहुभुज, जो इस तरह से परिभाषित है, सरल है यदि इन रेखा खंडों के केवल प्रतिच्छेदन बिंदु साझा अंतिम बिंदु पर हैं।^[2]

कुछ लेखक केवल उन बिंदुओं के लिए बहुभुजीकरण पर विचार करते हैं जो सामान्य स्थिति में हैं, जिसका अर्थ है कि कोई भी तीन एक पंक्ति में नहीं हैं।^[7] इस धारणा के साथ, बहुभुज के दो क्रमिक खंडों के बीच का कोण 180° नहीं हो सकता। हालाँकि, जब संरेखताओं वाले बिंदु सेटों पर विचार किया जाता है, तो आम तौर पर उनके बहुभुजीकरण के लिए कुछ बिंदुओं पर 180° कोण रखने की अनुमति दी जाती है। जब ऐसा होता है, तब भी इन बिंदुओं को किनारों के आंतरिक होने के स्थान पर शीर्ष ही माना जाता है।^[8]

अस्तित्व

ए का बहुभुजीकरण 3 × 3 जाल। प्रत्येक बहुभुज में दिखाई देने वाले 180° के कोण आवश्यक हैं: इस आकार के ग्रिड के लिए, सभी बहुभुजों में 180° का कोण होता है।^[9]

स्टीनहॉस (1964) ने देखा कि एक पंक्ति में तीन के बिना सेट किया गया प्रत्येक परिमित बिंदु एक साधारण बहुभुज के शीर्ष बनाता है।^[10] हालाँकि, किसी भी तीन को एक पंक्ति में होने की आवश्यकता अनावश्यक रूप से पर्याप्त है। इसके स्थान पर, बहुभुजीकरण (180° कोणों की अनुमति) के अस्तित्व के लिए केवल इतना आवश्यक है कि सभी बिंदु एक ही रेखा पर न हों। यदि वे ऐसा नहीं करते हैं, तो उनके पास एक बहुभुजीकरण है जिसे बहुपद समय में बनाया जा सकता है। बहुभुज बनाने का एक तरीका यह है कि $P$ के उत्तल संचालन में कोई बिंदु $q$ चुनें (जरूरी नहीं कि दिए गए बिंदुओं में से एक हो)। फिर q के चारों ओर के बिंदुओं को रेडियल रूप से क्रमबद्ध करना ( $q$ से दूरी के आधार पर संबंधों को तोड़ना) सभी दिए गए बिंदुओं के माध्यम से एक तारे के आकार के बहुभुज के चक्रीय क्रम को उत्पन्न करता है, जिसके कर्नेल में $q$ होता है।^[7] एक केंद्रीय बिंदु के चारों ओर रेडियल रूप से बिंदुओं को क्रमबद्ध करने का एक ही विचार ग्राहम स्कैन उत्तल संचालन एल्गोरिदम के कुछ संस्करणों में उपयोग किया जाता है, $O(n\log n)$ समय में निष्पादित किया जा सकता है।^[11]180° कोणों से बचने वाले बहुभुजीकरण हमेशा मौजूद नहीं होते हैं। उदाहरण के लिए, 3 × 3 और 5 × 5 वर्ग ग्रिड के लिए, सभी बहुभुजीकरण 180° कोणों का उपयोग करते हैं।^[9]

तारे के आकार के बहुभुजीकरण के साथ-साथ, बिंदुओं के प्रत्येक गैर-संरेखीय सेट में एक बहुभुजीकरण होता है जो एक मोनोटोन बहुभुज है। इसका मतलब यह है कि, कुछ सीधी रेखाओं के संबंध में (जिन्हें $x$ -अक्ष इस रूप में लिया जा सकता है) संदर्भ रेखा की प्रत्येक लंबवत रेखा बहुभुज को एक ही अंतराल में प्रतिच्छेद करती है, या बिल्कुल नहीं। ग्रुनबाम (1994) का निर्माण बिंदुओं को उनके $x$ -निर्देशांक के अनुसार क्रमबद्ध करने और दो चरम बिंदुओं के माध्यम से एक रेखा खींचने से शुरू होता है। क्योंकि सभी बिंदु एक पंक्ति में नहीं हैं, इस रेखा से घिरे दो खुले आधे तलों में से कम से कम एक गैर-रिक्त होना चाहिए। ग्रुनबाम दो मोनोटोन बहुभुज श्रृंखलाएं बनाता है जो चरम बिंदुओं को बिंदुओं के क्रमबद्ध अनुवर्ती के माध्यम से जोड़ता है: एक इस गैर-खाली खुले आधे विमान में बिंदुओं के लिए, और दूसरा शेष बिंदुओं के लिए। उनका संघ वांछित मोनोटोन बहुभुज है। श्रेणीकरण चरण के बाद, शेष निर्माण रैखिक समय में किया जा सकता है।^[4]

केवल अक्ष-समानांतर किनारों का उपयोग करके यह निर्धारित करना एनपी-पूर्ण है कि बिंदुओं के एक सेट में बहुभुजीकरण है या नहीं।^[12] हालाँकि, अतिरिक्त बाधा के साथ बहुभुजीकरण कि वे प्रत्येक शीर्ष पर दाएँ मुड़ते हैं, यदि वे मौजूद हैं, तो विशिष्ट रूप से निर्धारित होते हैं। एक बिंदु से होकर गुजरने वाली प्रत्येक अक्ष-समानांतर रेखा को सम संख्या में बिंदुओं से होकर गुजरना होगा, और इस बहुभुजीकरण को इस रेखा पर बिंदुओं के वैकल्पिक जोड़े को जोड़ना होगा। बहुभुजीकरण समय पर पाया जा सकता है $O(n\log n)$ बिंदुओं को समान निर्देशांक के आधार पर समूहित करके और प्रत्येक समूह को दूसरे निर्देशांक के आधार पर क्रमबद्ध करके।^[13] किसी भी बिंदु सेट के लिए, अधिकतम एक घुमाव में इस रूप का बहुभुजीकरण हो सकता है, और यह घुमाव फिर से बहुपद समय में पाया जा सकता है।^[14]

अनुकूलन

Unsolved problem in mathematics:

What is the computational complexity of the longest polygonalization?

(more unsolved problems in mathematics)

एक इष्टतम बहुभुजीकरण (इष्टतमता के विभिन्न मानदंडों के लिए) खोजने की समस्याएं अक्सर कम्प्यूटेशनल रूप से संभव नहीं होती हैं। उदाहरण के लिए, दिए गए बिंदुओं के लिए ट्रैवलिंग सेल्समैन समस्या के समाधान में कोई क्रॉसिंग नहीं है। इसलिए, यह हमेशा बहुभुजीकरण होता है, न्यूनतम परिधि वाला बहुभुजीकरण।^[15] इसे ढूंढना एनपी-कठिन है। इसी प्रकार, न्यूनतम या अधिकतम क्षेत्रफल वाले सरल बहुभुजीकरण को एनपी कठिन के रूप में जाना जाता है,^[3] और कुछ कम्प्यूटेशनल प्रयासों का विषय रहा है।^[16]^[17] अधिकतम क्षेत्रफल हमेशा उत्तल संचालन के क्षेत्रफल के आधे से अधिक होता है, जो 2 का अनुमानित अनुपात देता है।^[18] अधिकतम परिधि वाले सरल बहुभुजीकरण की सटीक जटिलता, और इस समस्या के लिए एक स्थिर सन्निकटन अनुपात का अस्तित्व अज्ञात रहता है।^[5] बहुभुजीकरण जो इसके सबसे लंबे किनारे की लंबाई को कम करता है, उसे ढूंढना भी एनपी-कठिन है, और इससे बेहतर अनुमानित अनुपात का अनुमान लगाना कठिन है ${\sqrt {3}}$ ; कोई स्थिर-कारक सन्निकटन ज्ञात नहीं है।^[19]

ट्रैवलिंग सेल्समैन समस्या के गैर-इष्टतम समाधान में क्रॉसिंग हो सकती है, लेकिन स्थानीय अनुकूलन चरणों द्वारा सभी क्रॉसिंग को खत्म करना संभव है जो कुल लंबाई को कम करते हैं। ऐसे चरणों का उपयोग करके जो प्रत्येक चरण पर क्रॉसिंग को भी समाप्त करते हैं, यह बहुपद समय में किया जा सकता है,^[20] लेकिन इस प्रतिबंध के बिना स्थानीय अनुकूलन अनुक्रम मौजूद हैं जो इसके स्थान पर चरणों की एक घातीय संख्या का उपयोग करते हैं।^[21]

सबसे छोटा बिटोनिक टूर (दिए गए बिंदुओं के माध्यम से न्यूनतम-परिधि मोनोटोन बहुभुज) हमेशा एक बहुभुज होता है, और बहुपद समय में पाया जा सकता है।^[22]

गिनती

Unsolved problem in mathematics:

What is the computational complexity of counting polygonalizations?

(more unsolved problems in mathematics)

किसी दिए गए बिंदु सेट के सभी बहुभुजों को गिनने की समस्या ♯P|#P से संबंधित है, जो एनपी (जटिलता) में निर्णय समस्याओं से जुड़ी समस्याओं की गिनती की श्रेणी है। हालाँकि, यह अज्ञात है कि क्या यह ♯P-complete|#P-complete है या, यदि नहीं, तो इसकी कम्प्यूटेशनल जटिलता क्या हो सकती है।^[23]^[24] बिंदुओं के एक सेट में बिल्कुल एक बहुभुजीकरण होता है यदि और केवल यदि यह उत्तल स्थिति में हो।^[1] के सेट मौजूद हैं $n$ वे बिंदु जिनके लिए बहुभुजीकरणों की संख्या उतनी ही बड़ी है $4.64^{n}$ ,^[25] और प्रत्येक सेट $n$ अंक अधिकतम है $54.6^{n}$ बहुभुजीकरण.^[6]

समतल विभाजक प्रमेय को लेबल किए गए बिंदु-सेट त्रिभुज पर लागू करने के तरीकों का उपयोग किसी सेट के सभी बहुभुजीकरणों को गिनने के लिए किया जा सकता है। $n$ उपघातीय समय में अंक, $n^{O({\sqrt {n}})}$ .^[26] गतिशील प्रोग्रामिंग का उपयोग बहुपद समय में सभी मोनोटोन बहुभुजीकरणों को गिनने के लिए किया जा सकता है, और इस गणना के परिणामों का उपयोग यादृच्छिक मोनोटोन बहुभुजीकरण उत्पन्न करने के लिए किया जा सकता है।^[27]

पीढ़ी

Unsolved problem in mathematics:

Can local moves connect the state space of polygonalizations for every point set?

(more unsolved problems in mathematics)

एक बहुभुज जिसे फ्लिप या वीई-फ्लिप द्वारा समान बिंदुओं के माध्यम से किसी अन्य बहुभुज में नहीं बदला जा सकता है^[28]

यह अज्ञात है कि क्या सभी बहुभुजीकरणों की प्रणाली के लिए स्थानीय चालों के तहत एक कनेक्टेड राज्य अंतरिक्ष बनाना संभव है जो बहुभुजीकरणों के किनारों की एक सीमित संख्या को बदलता है। यदि यह संभव होता, तो इसे राज्य स्थान पर ग्राफ़ ट्रैवर्सल लागू करके, सभी बहुभुजीकरण उत्पन्न करने के लिए एल्गोरिदम के हिस्से के रूप में उपयोग किया जा सकता था। इस समस्या के लिए, उन फ़्लिपों पर विचार करना अपर्याप्त है जो बहुभुज के दो किनारों को हटाते हैं और उन्हें दो अन्य किनारों से प्रतिस्थापित करते हैं, या वीई-फ़्लिप्स जो तीन किनारों को हटाते हैं, जिनमें से दो एक शीर्ष साझा करते हैं, और उन्हें तीन अन्य किनारों से प्रतिस्थापित करते हैं। ऐसे बहुभुजीकरण मौजूद हैं जिनके लिए कोई फ्लिप या वीई-फ्लिप संभव नहीं है, भले ही समान बिंदु सेट में अन्य बहुभुजीकरण हों।^[28]

बहुभुज आवरण, कमज़ोर सरल बहुभुज जो प्रत्येक दिए गए बिंदु को एक या अधिक बार शीर्ष के रूप में उपयोग करते हैं, इसमें सभी बहुभुजीकरण शामिल होते हैं और स्थानीय चालों से जुड़े होते हैं।^[2] बहुभुजों का एक और अधिक सामान्य वर्ग, आसपास के बहुभुज, सरल बहुभुज होते हैं जिनमें दिए गए कुछ बिंदु शीर्ष के रूप में होते हैं और सभी बिंदुओं को घेरते हैं। वे फिर से स्थानीय रूप से जुड़े हुए हैं, और प्रति बहुभुज बहुपद समय में सूचीबद्ध किए जा सकते हैं। एल्गोरिथ्म बहुभुजों के एक पेड़ का निर्माण करता है, जिसकी जड़ उत्तल संचालन है और एक शीर्ष को हटाकर एक दूसरे के आसपास के बहुभुज के माता-पिता को प्राप्त किया जाता है (बहुभुज के बाहरी हिस्से में दो कान प्रमेय को लागू करने से यह संभव साबित होता है)। इसके बाद यह बहुभुजों को सूचीबद्ध करने के लिए इस पेड़ पर एक रिवर्स-सर्च एल्गोरिदम लागू करता है। इस पद्धति के परिणामस्वरूप, सभी बहुभुजीकरणों को ई (जटिलता) में सूचीबद्ध किया जा सकता है ( $2^{O(n)}$ के लिए $n$ अंक) और बहुपद स्थान।^[29]

अनुप्रयोग

क्लासिकल बिंदुओ को जोडो पहेलियों में कुछ अप्रत्याशित आकार बनाने के लिए बिंदुओं को क्रम से जोड़ना शामिल होता है, अक्सर बिना क्रॉसिंग के।^[30] ट्रैवलिंग सेल्समैन समस्या और इसके वेरिएंट के कई अनुप्रयोग हैं।^[31] बहुभुजीकरण का अनुप्रयोग बिखरे हुए डेटा बिंदुओं से समोच्च रेखाओं के पुनर्निर्माण और छवि विश्लेषण में सीमा अनुरेखण में भी होता है।^[32]

यह भी देखें

डेनजॉय-रिस्ज़ प्रमेय, अनंत बिंदुओं के सेट पर जिन्हें जॉर्डन आर्क द्वारा जोड़ा जा सकता है

संदर्भ

↑ ^1.0 ^1.1 Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph S. B.; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003), "On the reflexivity of point sets", in Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.), Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Algorithms and Combinatorics, vol. 25, Berlin: Springer, pp. 139–156, doi:10.1007/978-3-642-55566-4_6, MR 2038472
↑ ^2.0 ^2.1 ^2.2 Damian, Mirela; Flatland, Robin; O'Rourke, Joseph; Ramaswami, Suneeta (2010), "Connecting polygonizations via stretches and twangs", Theory of Computing Systems, 47 (3): 674–695, doi:10.1007/s00224-009-9192-8, MR 2652036, S2CID 59602
↑ ^3.0 ^3.1 Fekete, S. P. (2000), "On simple polygonalizations with optimal area", Discrete & Computational Geometry, 23 (1): 73–110, doi:10.1007/PL00009492, MR 1727124, S2CID 15835121
↑ ^4.0 ^4.1 Grünbaum, Branko (1994), "Hamiltonian polygons and polyhedra" (PDF), Geombinatorics, 3 (3): 83–89, MR 1326479
↑ ^5.0 ^5.1 Dumitrescu, Adrian; Tóth, Csaba D. (2010), "Long non-crossing configurations in the plane", Discrete & Computational Geometry, 44 (4): 727–752, doi:10.1007/s00454-010-9277-9, MR 2728029, S2CID 2813190
↑ ^6.0 ^6.1 Sharir, Micha; Sheffer, Adam; Welzl, Emo (2013), "Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique", Journal of Combinatorial Theory, Series A, 120 (4): 777–794, doi:10.1016/j.jcta.2013.01.002, MR 3022612
↑ ^7.0 ^7.1 Deneen, Linda; Shute, Gary (1988), "Polygonizations of point sets in the plane", Discrete & Computational Geometry, 3 (1): 77–87, doi:10.1007/BF02187898, MR 0918181
↑ Malkevitch, Joseph (2016), "Are Precise Definitions a Good Idea?", AMS Feature Column, American Mathematical Society
↑ ^9.0 ^9.1 Chow, Sam; Gafni, Ayla; Gafni, Paul (March 2021), "Connecting the dots: maximal polygons on a square grid", Mathematics Magazine, 94 (2): 118–124, doi:10.1080/0025570x.2021.1869493, MR 4241975, S2CID 233185771
↑ Steinhaus, Hugo (1964), One Hundred Problems in Elementary Mathematics, Basic Books, pp. 17, 85–86, ISBN 9780486811802
↑ Graham, R. L. (June 1972), "An efficient algorithm for determining the convex hull of a finite planar set" (PDF), Information Processing Letters, 1 (4): 132–133, doi:10.1016/0020-0190(72)90045-2
↑ Rappaport, David (1986), On the complexity of computing orthogonal polygons from a set of points, Technical Report, vol. SOCS-86.9, Montreal: McGill University
↑ O'Rourke, Joseph (1988), "Uniqueness of orthogonal connect-the-dots", in Toussaint, Godfried T. (ed.), Computational Morphology: A Computational Geometric Approach to the Analysis of Form, Machine Intelligence and Pattern Recognition, vol. 6, Amsterdam: North-Holland, pp. 97–104, doi:10.1016/B978-0-444-70467-2.50013-8, MR 0994001
↑ Löffler, Maarten; Mumford, Elena (2011), "Connected rectilinear graphs on point sets", Journal of Computational Geometry, 2 (1): 1–15, doi:10.20382/v2i1a1, MR 2786032
↑ Quintas, L. V.; Supnick, Fred (1965), "On some properties of shortest Hamiltonian circuits", The American Mathematical Monthly, 72 (9): 977–980, doi:10.2307/2313333, JSTOR 2313333, MR 0188872
↑ Demaine, Erik D.; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph S. B. (2022), "Area-optimal simple polygonalizations: the CG challenge 2019", ACM Journal of Experimental Algorithmics, 27: Art. 2.4, 12, doi:10.1145/3504000, MR 4390039, S2CID 244117500
↑ Ramos, Natanael; de Rezende, Pedro J.; de Souza, Cid C. (2022), "Optimal area polygonization problems: exact solutions through geometric duality", Computers & Operations Research, 145, Paper No. 105842, doi:10.1016/j.cor.2022.105842, MR 4418151, S2CID 248369389
↑ Fekete, Sándor P. (1992), Geometry and the Travelling Salesman Problem (Doctoral dissertation), University of Waterloo, ProQuest 304035266 For a polygonalization of area more than half the convex hull, see Theorem 4.2.1, page 56.
↑ Fekete, Sándor P.; Keldenich, Phillip (2018), "Computing crossing-free configurations with minimum bottleneck" (PDF), 34th European Workshop on Computational Geometry, Free University of Berlin, pp. 23:1–23:6
↑ van Leeuwen, Jan; Schoone, Anneke A. (1981), "Untangling a travelling salesman tour in the plane" (PDF), in Mühlbacher, Jörg R. (ed.), Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), Linz, Austria, June 15-17, 1981, Hanser, Munich, pp. 87–98, MR 0708744
↑ Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2014), "Worst case and probabilistic analysis of the 2-opt algorithm for the TSP", Algorithmica, 68 (1): 190–264, doi:10.1007/s00453-013-9801-4, MR 3147481, S2CID 1638275
↑ de Berg, Mark; Buchin, Kevin; Jansen, Bart M. P.; Woeginger, Gerhard (2016), "Fine-Grained Complexity Analysis of Two Classic TSP Variants", in Chatzigiannakis, Ioannis; Mitzenmacher, Michael; Rabani, Yuval; Sangiorgi, Davide (eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 5:1–5:14, doi:10.4230/LIPIcs.ICALP.2016.5, ISBN 978-3-95977-013-2
↑ Mitchell, Joseph S. B.; O'Rourke, Joseph (2001), "Computational geometry column 42", International Journal of Computational Geometry and Applications, 11 (5): 573–582, arXiv:cs/0108021, doi:10.1142/S0218195901000651, MR 1862888
↑ O'Rourke, Joseph (January 1, 2003), "Problem 16: Simple Polygonalizations", The Open Problems Project
↑ García, Alfredo; Noy, Marc; Tejel, Javier (2000), "Lower bounds on the number of crossing-free subgraphs of $K_{N}$ ", Computational Geometry: Theory & Applications, 16 (4): 211–221, doi:10.1016/S0925-7721(00)00010-9, MR 1775294
↑ Marx, Dániel; Miltzow, Tillmann (2016), "Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems", in Fekete, Sándor P.; Lubiw, Anna (eds.), 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, LIPIcs, vol. 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 52:1–52:16, arXiv:1603.07340, doi:10.4230/LIPIcs.SoCG.2016.52, ISBN 9783959770095, MR 3540894, S2CID 7668194
↑ Zhu, Chong; Sundaram, Gopalakrishnan; Snoeyink, Jack; Mitchell, Joseph S. B. (1996), "Generating random polygons with given vertices", Computational Geometry: Theory & Applications, 6 (5): 277–290, doi:10.1016/0925-7721(95)00031-3, MR 1408922
↑ ^28.0 ^28.1 Hernando, Carmen; Houle, Michael E.; Hurtado, Ferran (2002), "On local transformation of polygons with visibility properties", Theoretical Computer Science, 289 (2): 919–937, doi:10.1016/S0304-3975(01)00409-1, MR 1945256
↑ Yamanaka, Katsuhisa; Avis, David; Horiyama, Takashi; Okamoto, Yoshio; Uehara, Ryuhei; Yamauchi, Tanami (2021), "Algorithmic enumeration of surrounding polygons" (PDF), Discrete Applied Mathematics, 303: 305–313, doi:10.1016/j.dam.2020.03.034, MR 4310502
↑ Löffler, Maarten; Kaiser, Mira; van Kapel, Tim; Klappe, Gerwin; van Kreveld, Marc J.; Staals, Frank (2014), "The Connect-The-Dots family of puzzles: design and automatic generation", ACM Transactions on Graphics, 33 (4): 72:1–72:10, doi:10.1145/2601097.2601224, S2CID 9774101
↑ Cook, William J. (2012), "Chapter 3: The salesman in action", In pursuit of the traveling salesman, Princeton University Press, Princeton, NJ, pp. 44–61, ISBN 978-0-691-15270-7, MR 2866515
↑ Stelldinger, Peer (2010), "Connect the dots: the reconstruction of region boundaries from contour sampling points", in Köthe, Ullrich; Montanvert, Annick; Soille, Pierre (eds.), Applications of Discrete Geometry and Mathematical Morphology - First International Workshop, WADGMM 2010, Istanbul, Turkey, August 22, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7346, Springer, pp. 1–13, doi:10.1007/978-3-642-32313-3_1

[reflexivity-1] 1.0 ^1.1 Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph S. B.; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003), "On the reflexivity of point sets", in Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.), Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Algorithms and Combinatorics, vol. 25, Berlin: Springer, pp. 139–156, doi:10.1007/978-3-642-55566-4_6, MR 2038472

[dfor-2] 2.0 ^2.1 ^2.2 Damian, Mirela; Flatland, Robin; O'Rourke, Joseph; Ramaswami, Suneeta (2010), "Connecting polygonizations via stretches and twangs", Theory of Computing Systems, 47 (3): 674–695, doi:10.1007/s00224-009-9192-8, MR 2652036, S2CID 59602

[fekete-3] 3.0 ^3.1 Fekete, S. P. (2000), "On simple polygonalizations with optimal area", Discrete & Computational Geometry, 23 (1): 73–110, doi:10.1007/PL00009492, MR 1727124, S2CID 15835121

[grunbaum-4] 4.0 ^4.1 Grünbaum, Branko (1994), "Hamiltonian polygons and polyhedra" (PDF), Geombinatorics, 3 (3): 83–89, MR 1326479

[long-5] 5.0 ^5.1 Dumitrescu, Adrian; Tóth, Csaba D. (2010), "Long non-crossing configurations in the plane", Discrete & Computational Geometry, 44 (4): 727–752, doi:10.1007/s00454-010-9277-9, MR 2728029, S2CID 2813190

[ssw-6] 6.0 ^6.1 Sharir, Micha; Sheffer, Adam; Welzl, Emo (2013), "Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique", Journal of Combinatorial Theory, Series A, 120 (4): 777–794, doi:10.1016/j.jcta.2013.01.002, MR 3022612

[star-shaped-7] 7.0 ^7.1 Deneen, Linda; Shute, Gary (1988), "Polygonizations of point sets in the plane", Discrete & Computational Geometry, 3 (1): 77–87, doi:10.1007/BF02187898, MR 0918181

[precise-8] Malkevitch, Joseph (2016), "Are Precise Definitions a Good Idea?", AMS Feature Column, American Mathematical Society

[grid-9] 9.0 ^9.1 Chow, Sam; Gafni, Ayla; Gafni, Paul (March 2021), "Connecting the dots: maximal polygons on a square grid", Mathematics Magazine, 94 (2): 118–124, doi:10.1080/0025570x.2021.1869493, MR 4241975, S2CID 233185771

[steinhaus-10] Steinhaus, Hugo (1964), One Hundred Problems in Elementary Mathematics, Basic Books, pp. 17, 85–86, ISBN 9780486811802

[graham-11] Graham, R. L. (June 1972), "An efficient algorithm for determining the convex hull of a finite planar set" (PDF), Information Processing Letters, 1 (4): 132–133, doi:10.1016/0020-0190(72)90045-2

[rappaport-12] Rappaport, David (1986), On the complexity of computing orthogonal polygons from a set of points, Technical Report, vol. SOCS-86.9, Montreal: McGill University

[orthogonal-13] O'Rourke, Joseph (1988), "Uniqueness of orthogonal connect-the-dots", in Toussaint, Godfried T. (ed.), Computational Morphology: A Computational Geometric Approach to the Analysis of Form, Machine Intelligence and Pattern Recognition, vol. 6, Amsterdam: North-Holland, pp. 97–104, doi:10.1016/B978-0-444-70467-2.50013-8, MR 0994001

[rotate-14] Löffler, Maarten; Mumford, Elena (2011), "Connected rectilinear graphs on point sets", Journal of Computational Geometry, 2 (1): 1–15, doi:10.20382/v2i1a1, MR 2786032

[qs-15] Quintas, L. V.; Supnick, Fred (1965), "On some properties of shortest Hamiltonian circuits", The American Mathematical Monthly, 72 (9): 977–980, doi:10.2307/2313333, JSTOR 2313333, MR 0188872

[contest-16] Demaine, Erik D.; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph S. B. (2022), "Area-optimal simple polygonalizations: the CG challenge 2019", ACM Journal of Experimental Algorithmics, 27: Art. 2.4, 12, doi:10.1145/3504000, MR 4390039, S2CID 244117500

[area-ilp-17] Ramos, Natanael; de Rezende, Pedro J.; de Souza, Cid C. (2022), "Optimal area polygonization problems: exact solutions through geometric duality", Computers & Operations Research, 145, Paper No. 105842, doi:10.1016/j.cor.2022.105842, MR 4418151, S2CID 248369389

[tsp-18] Fekete, Sándor P. (1992), Geometry and the Travelling Salesman Problem (Doctoral dissertation), University of Waterloo, ProQuest 304035266 For a polygonalization of area more than half the convex hull, see Theorem 4.2.1, page 56.

[bottleneck-19] Fekete, Sándor P.; Keldenich, Phillip (2018), "Computing crossing-free configurations with minimum bottleneck" (PDF), 34th European Workshop on Computational Geometry, Free University of Berlin, pp. 23:1–23:6

[vls-20] van Leeuwen, Jan; Schoone, Anneke A. (1981), "Untangling a travelling salesman tour in the plane" (PDF), in Mühlbacher, Jörg R. (ed.), Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), Linz, Austria, June 15-17, 1981, Hanser, Munich, pp. 87–98, MR 0708744

[erv-21] Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2014), "Worst case and probabilistic analysis of the 2-opt algorithm for the TSP", Algorithmica, 68 (1): 190–264, doi:10.1007/s00453-013-9801-4, MR 3147481, S2CID 1638275

[bbjw-22] Berg, Mark; Buchin, Kevin; Jansen, Bart M. P.; Woeginger, Gerhard (2016), "Fine-Grained Complexity Analysis of Two Classic TSP Variants", in Chatzigiannakis, Ioannis; Mitzenmacher, Michael; Rabani, Yuval; Sangiorgi, Davide (eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 5:1–5:14, doi:10.4230/LIPIcs.ICALP.2016.5, ISBN 978-3-95977-013-2

[cg42-23] Mitchell, Joseph S. B.; O'Rourke, Joseph (2001), "Computational geometry column 42", International Journal of Computational Geometry and Applications, 11 (5): 573–582, arXiv:cs/0108021, doi:10.1142/S0218195901000651, MR 1862888

[topp-24] O'Rourke, Joseph (January 1, 2003), "Problem 16: Simple Polygonalizations", The Open Problems Project

[gnt-25] García, Alfredo; Noy, Marc; Tejel, Javier (2000), "Lower bounds on the number of crossing-free subgraphs of $K_{N}$ ", Computational Geometry: Theory & Applications, 16 (4): 211–221, doi:10.1016/S0925-7721(00)00010-9, MR 1775294

[cactus-26] Marx, Dániel; Miltzow, Tillmann (2016), "Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems", in Fekete, Sándor P.; Lubiw, Anna (eds.), 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, LIPIcs, vol. 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 52:1–52:16, arXiv:1603.07340, doi:10.4230/LIPIcs.SoCG.2016.52, ISBN 9783959770095, MR 3540894, S2CID 7668194

[zssm-27] Zhu, Chong; Sundaram, Gopalakrishnan; Snoeyink, Jack; Mitchell, Joseph S. B. (1996), "Generating random polygons with given vertices", Computational Geometry: Theory & Applications, 6 (5): 277–290, doi:10.1016/0925-7721(95)00031-3, MR 1408922

[hhh-28] 28.0 ^28.1 Hernando, Carmen; Houle, Michael E.; Hurtado, Ferran (2002), "On local transformation of polygons with visibility properties", Theoretical Computer Science, 289 (2): 919–937, doi:10.1016/S0304-3975(01)00409-1, MR 1945256

[yahouy-29] Yamanaka, Katsuhisa; Avis, David; Horiyama, Takashi; Okamoto, Yoshio; Uehara, Ryuhei; Yamauchi, Tanami (2021), "Algorithmic enumeration of surrounding polygons" (PDF), Discrete Applied Mathematics, 303: 305–313, doi:10.1016/j.dam.2020.03.034, MR 4310502

[ctd-30] Löffler, Maarten; Kaiser, Mira; van Kapel, Tim; Klappe, Gerwin; van Kreveld, Marc J.; Staals, Frank (2014), "The Connect-The-Dots family of puzzles: design and automatic generation", ACM Transactions on Graphics, 33 (4): 72:1–72:10, doi:10.1145/2601097.2601224, S2CID 9774101

[pursuit-31] Cook, William J. (2012), "Chapter 3: The salesman in action", In pursuit of the traveling salesman, Princeton University Press, Princeton, NJ, pp. 44–61, ISBN 978-0-691-15270-7, MR 2866515

[contour-32] Stelldinger, Peer (2010), "Connect the dots: the reconstruction of region boundaries from contour sampling points", in Köthe, Ullrich; Montanvert, Annick; Soille, Pierre (eds.), Applications of Discrete Geometry and Mathematical Morphology - First International Workshop, WADGMM 2010, Istanbul, Turkey, August 22, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7346, Springer, pp. 1–13, doi:10.1007/978-3-642-32313-3_1

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

@@ Line 14: / Line 14: @@
 ==अस्तित्व==
 [[File:3x3 grid polygonalizations.svg|thumb|ए का बहुभुजीकरण {{nowrap|3 × 3}} जाल। प्रत्येक बहुभुज में दिखाई देने वाले 180° के कोण आवश्यक हैं: इस आकार के ग्रिड के लिए, सभी बहुभुजों में 180° का कोण होता है।{{r|grid}}]]
-{{harvtxt|Steinhaus|1964}} देखा गया कि एक पंक्ति में तीन के बिना सेट किया गया प्रत्येक परिमित बिंदु एक साधारण बहुभुज के शीर्ष बनाता है।{{r|steinhaus}} हालाँकि, एक पंक्ति में तीन लोगों के होने की आवश्यकता अनावश्यक रूप से मजबूत है। इसके स्थान पर, बहुभुजीकरण (180° कोणों की अनुमति) के अस्तित्व के लिए केवल इतना आवश्यक है कि सभी बिंदु एक रेखा पर न हों। यदि वे ऐसा नहीं करते हैं, तो उनके पास एक बहुभुजीकरण है जिसका निर्माण बहुपद समय में किया जा सकता है। बहुभुज बनाने का एक तरीका किसी भी बिंदु को चुनना है <math>q</math> के उत्तल पतवार में <math>P</math> (जरूरी नहीं कि दिए गए बिंदुओं में से एक हो)। फिर चारों ओर के बिंदुओं को रेडियल रूप से व्यवस्थित करना <math>q</math> (क्यू से दूरी के आधार पर संबंधों को तोड़ना) सभी दिए गए बिंदुओं के माध्यम से एक तारे के आकार के बहुभुज के चक्रीय क्रम का निर्माण करता है <math>q</math> इसके कर्नेल में.{{r|star-shaped}} एक केंद्रीय बिंदु के चारों ओर रेडियल रूप से बिंदुओं को क्रमबद्ध करने का एक ही विचार [[ग्राहम स्कैन]] उत्तल हल एल्गोरिथ्म के कुछ संस्करणों में उपयोग किया जाता है, और इसमें प्रदर्शन किया जा सकता है <math>O(n\log n)</math> समय।{{r|graham}} 180° कोणों से बचने वाले बहुभुजीकरण हमेशा मौजूद नहीं होते हैं। उदाहरण के लिए, के लिए {{nowrap|3 × 3}} और {{nowrap|5 × 5}} वर्गाकार ग्रिड, सभी बहुभुजीकरण 180° कोणों का उपयोग करते हैं।{{r|grid}}
+स्टीनहॉस (1964) ने देखा कि एक पंक्ति में तीन के बिना सेट किया गया प्रत्येक परिमित बिंदु एक साधारण बहुभुज के शीर्ष बनाता है।{{r|steinhaus}} हालाँकि, किसी भी तीन को एक पंक्ति में होने की आवश्यकता अनावश्यक रूप से पर्याप्त है। इसके स्थान पर, बहुभुजीकरण (180° कोणों की अनुमति) के अस्तित्व के लिए केवल इतना आवश्यक है कि सभी बिंदु एक ही रेखा पर न हों। यदि वे ऐसा नहीं करते हैं, तो उनके पास एक बहुभुजीकरण है जिसे बहुपद समय में बनाया जा सकता है। बहुभुज बनाने का एक तरीका यह है कि <math>P</math> के उत्तल संचालन में कोई बिंदु <math>q</math> चुनें (जरूरी नहीं कि दिए गए बिंदुओं में से एक हो)। फिर q के चारों ओर के बिंदुओं को रेडियल रूप से क्रमबद्ध करना (<math>q</math> से दूरी के आधार पर संबंधों को तोड़ना) सभी दिए गए बिंदुओं के माध्यम से एक तारे के आकार के बहुभुज के चक्रीय क्रम को उत्पन्न करता है, जिसके कर्नेल में <math>q</math> होता है।{{r|star-shaped}} एक केंद्रीय बिंदु के चारों ओर रेडियल रूप से बिंदुओं को क्रमबद्ध करने का एक ही विचार [[ग्राहम स्कैन]] उत्तल संचालन एल्गोरिदम के कुछ संस्करणों में उपयोग किया जाता है,<math>O(n\log n)</math> समय में निष्पादित किया जा सकता है।{{r|graham}}180° कोणों से बचने वाले बहुभुजीकरण हमेशा मौजूद नहीं होते हैं। उदाहरण के लिए, 3 × 3 और 5 × 5 वर्ग ग्रिड के लिए, सभी बहुभुजीकरण 180° कोणों का उपयोग करते हैं।{{r|grid}}
+तारे के आकार के बहुभुजीकरण के साथ-साथ, बिंदुओं के प्रत्येक गैर-संरेखीय सेट में एक बहुभुजीकरण होता है जो एक [[मोनोटोन बहुभुज]] है। इसका मतलब यह है कि, कुछ सीधी रेखाओं के संबंध में (जिन्हें <math>x</math>-अक्ष इस रूप में लिया जा सकता है) संदर्भ रेखा की प्रत्येक लंबवत रेखा बहुभुज को एक ही अंतराल में प्रतिच्छेद करती है, या बिल्कुल नहीं। ग्रुनबाम (1994) का निर्माण बिंदुओं को उनके <math>x</math>-निर्देशांक के अनुसार क्रमबद्ध करने और दो चरम बिंदुओं के माध्यम से एक रेखा खींचने से शुरू होता है। क्योंकि सभी बिंदु एक पंक्ति में नहीं हैं, इस रेखा से घिरे दो खुले आधे तलों में से कम से कम एक गैर-रिक्त होना चाहिए। ग्रुनबाम दो मोनोटोन [[बहुभुज श्रृंखला]]एं बनाता है जो चरम बिंदुओं को बिंदुओं के क्रमबद्ध अनुवर्ती के माध्यम से जोड़ता है: एक इस गैर-खाली खुले आधे विमान में बिंदुओं के लिए, और दूसरा शेष बिंदुओं के लिए। उनका संघ वांछित मोनोटोन बहुभुज है। श्रेणीकरण चरण के बाद, शेष निर्माण रैखिक समय में किया जा सकता है।{{r|grunbaum}}
-तारे के आकार के बहुभुजीकरण के साथ-साथ, बिंदुओं के प्रत्येक गैर-संरेखीय सेट में एक बहुभुजीकरण होता है जो एक [[मोनोटोन बहुभुज]] होता है। इसका मतलब यह है कि, कुछ सीधी रेखा के संबंध में (जिसे लिया जा सकता है <math>x</math>-अक्ष) संदर्भ रेखा की प्रत्येक लंबवत रेखा बहुभुज को एक ही अंतराल में काटती है, या बिल्कुल नहीं। का एक निर्माण {{harvtxt|Grünbaum|1994}} अंकों को उनके आधार पर क्रमबद्ध करने से शुरू होता है <math>x</math>-निर्देशांक, और दो चरम बिंदुओं के माध्यम से एक रेखा खींचना। चूँकि सभी बिंदु एक रेखा में नहीं हैं, इस रेखा से घिरे दो खुले आधे तलों में से कम से कम एक गैर-रिक्त होना चाहिए। ग्रुनबाम दो मोनोटोन [[बहुभुज श्रृंखला]]एं बनाता है जो बिंदुओं के क्रमबद्ध अनुवर्ती के माध्यम से चरम बिंदुओं को जोड़ता है: एक इस गैर-खाली खुले आधे विमान में बिंदुओं के लिए, और दूसरा शेष बिंदुओं के लिए। उनका मिलन वांछित एकस्वर बहुभुज है। छँटाई चरण के बाद, शेष निर्माण [[रैखिक समय]] में किया जा सकता है।{{r|grunbaum}}
 केवल अक्ष-समानांतर किनारों का उपयोग करके यह निर्धारित करना एनपी-पूर्ण है कि बिंदुओं के एक सेट में बहुभुजीकरण है या नहीं।{{r|rappaport}} हालाँकि, अतिरिक्त बाधा के साथ बहुभुजीकरण कि वे प्रत्येक शीर्ष पर दाएँ मुड़ते हैं, यदि वे मौजूद हैं, तो विशिष्ट रूप से निर्धारित होते हैं। एक बिंदु से होकर गुजरने वाली प्रत्येक अक्ष-समानांतर रेखा को सम संख्या में बिंदुओं से होकर गुजरना होगा, और इस बहुभुजीकरण को इस रेखा पर बिंदुओं के वैकल्पिक जोड़े को जोड़ना होगा। बहुभुजीकरण समय पर पाया जा सकता है <math>O(n\log n)</math> बिंदुओं को समान निर्देशांक के आधार पर समूहित करके और प्रत्येक समूह को दूसरे निर्देशांक के आधार पर क्रमबद्ध करके।{{r|orthogonal}} किसी भी बिंदु सेट के लिए, अधिकतम एक घुमाव में इस रूप का बहुभुजीकरण हो सकता है, और यह घुमाव फिर से बहुपद समय में पाया जा सकता है।{{r|rotate}}
@@ Line 24: / Line 25: @@
 ==अनुकूलन==
 {{unsolved|mathematics|What is the computational complexity of the longest polygonalization?}}
-एक इष्टतम बहुभुजीकरण (इष्टतमता के विभिन्न मानदंडों के लिए) खोजने की समस्याएं अक्सर कम्प्यूटेशनल रूप से संभव नहीं होती हैं। उदाहरण के लिए, दिए गए बिंदुओं के लिए ट्रैवलिंग सेल्समैन समस्या के समाधान में कोई क्रॉसिंग नहीं है। इसलिए, यह हमेशा बहुभुजीकरण होता है, न्यूनतम परिधि वाला बहुभुजीकरण।{{r|qs}} इसे ढूंढना एनपी-कठिन है। इसी प्रकार, न्यूनतम या अधिकतम क्षेत्रफल वाले सरल बहुभुजीकरण को [[ एनपी कठिन ]] के रूप में जाना जाता है,{{r|fekete}} और कुछ कम्प्यूटेशनल प्रयासों का विषय रहा है।{{r|contest|area-ilp}} अधिकतम क्षेत्रफल हमेशा उत्तल पतवार के क्षेत्रफल के आधे से अधिक होता है, जो 2 का अनुमानित अनुपात देता है।{{r|tsp}} अधिकतम परिधि वाले सरल बहुभुजीकरण की सटीक जटिलता, और इस समस्या के लिए एक स्थिर सन्निकटन अनुपात का अस्तित्व अज्ञात रहता है।{{r|long}} बहुभुजीकरण जो इसके सबसे लंबे किनारे की लंबाई को कम करता है, उसे ढूंढना भी एनपी-कठिन है, और इससे बेहतर अनुमानित अनुपात का अनुमान लगाना कठिन है <math>\sqrt3</math>; कोई स्थिर-कारक सन्निकटन ज्ञात नहीं है।{{r|bottleneck}}
+एक इष्टतम बहुभुजीकरण (इष्टतमता के विभिन्न मानदंडों के लिए) खोजने की समस्याएं अक्सर कम्प्यूटेशनल रूप से संभव नहीं होती हैं। उदाहरण के लिए, दिए गए बिंदुओं के लिए ट्रैवलिंग सेल्समैन समस्या के समाधान में कोई क्रॉसिंग नहीं है। इसलिए, यह हमेशा बहुभुजीकरण होता है, न्यूनतम परिधि वाला बहुभुजीकरण।{{r|qs}} इसे ढूंढना एनपी-कठिन है। इसी प्रकार, न्यूनतम या अधिकतम क्षेत्रफल वाले सरल बहुभुजीकरण को [[ एनपी कठिन ]] के रूप में जाना जाता है,{{r|fekete}} और कुछ कम्प्यूटेशनल प्रयासों का विषय रहा है।{{r|contest|area-ilp}} अधिकतम क्षेत्रफल हमेशा उत्तल संचालन के क्षेत्रफल के आधे से अधिक होता है, जो 2 का अनुमानित अनुपात देता है।{{r|tsp}} अधिकतम परिधि वाले सरल बहुभुजीकरण की सटीक जटिलता, और इस समस्या के लिए एक स्थिर सन्निकटन अनुपात का अस्तित्व अज्ञात रहता है।{{r|long}} बहुभुजीकरण जो इसके सबसे लंबे किनारे की लंबाई को कम करता है, उसे ढूंढना भी एनपी-कठिन है, और इससे बेहतर अनुमानित अनुपात का अनुमान लगाना कठिन है <math>\sqrt3</math>; कोई स्थिर-कारक सन्निकटन ज्ञात नहीं है।{{r|bottleneck}}
 ट्रैवलिंग सेल्समैन समस्या के गैर-इष्टतम समाधान में क्रॉसिंग हो सकती है, लेकिन स्थानीय अनुकूलन चरणों द्वारा सभी क्रॉसिंग को खत्म करना संभव है जो कुल लंबाई को कम करते हैं। ऐसे चरणों का उपयोग करके जो प्रत्येक चरण पर क्रॉसिंग को भी समाप्त करते हैं, यह बहुपद समय में किया जा सकता है,{{r|vls}} लेकिन इस प्रतिबंध के बिना स्थानीय अनुकूलन अनुक्रम मौजूद हैं जो इसके स्थान पर चरणों की एक घातीय संख्या का उपयोग करते हैं।{{r|erv}}
@@ Line 40: / Line 41: @@
 [[File:Unflippable polygon.svg|thumb|एक बहुभुज जिसे फ्लिप या वीई-फ्लिप द्वारा समान बिंदुओं के माध्यम से किसी अन्य बहुभुज में नहीं बदला जा सकता है{{r|hhh}}]]यह अज्ञात है कि क्या सभी बहुभुजीकरणों की प्रणाली के लिए स्थानीय चालों के तहत एक कनेक्टेड [[ राज्य अंतरिक्ष ]] बनाना संभव है जो बहुभुजीकरणों के किनारों की एक सीमित संख्या को बदलता है। यदि यह संभव होता, तो इसे राज्य स्थान पर [[ ग्राफ़ ट्रैवर्सल ]] लागू करके, सभी बहुभुजीकरण उत्पन्न करने के लिए एल्गोरिदम के हिस्से के रूप में उपयोग किया जा सकता था। इस समस्या के लिए, उन फ़्लिपों पर विचार करना अपर्याप्त है जो बहुभुज के दो किनारों को हटाते हैं और उन्हें दो अन्य किनारों से प्रतिस्थापित करते हैं, या वीई-फ़्लिप्स जो तीन किनारों को हटाते हैं, जिनमें से दो एक शीर्ष साझा करते हैं, और उन्हें तीन अन्य किनारों से प्रतिस्थापित करते हैं। ऐसे बहुभुजीकरण मौजूद हैं जिनके लिए कोई फ्लिप या वीई-फ्लिप संभव नहीं है, भले ही समान बिंदु सेट में अन्य बहुभुजीकरण हों।{{r|hhh}}
-बहुभुज आवरण, कमज़ोर सरल बहुभुज जो प्रत्येक दिए गए बिंदु को एक या अधिक बार शीर्ष के रूप में उपयोग करते हैं, इसमें सभी बहुभुजीकरण शामिल होते हैं और स्थानीय चालों से जुड़े होते हैं।{{r|dfor}} बहुभुजों का एक और अधिक सामान्य वर्ग, आसपास के बहुभुज, सरल बहुभुज होते हैं जिनमें दिए गए कुछ बिंदु शीर्ष के रूप में होते हैं और सभी बिंदुओं को घेरते हैं। वे फिर से स्थानीय रूप से जुड़े हुए हैं, और प्रति बहुभुज बहुपद समय में सूचीबद्ध किए जा सकते हैं। एल्गोरिथ्म बहुभुजों के एक पेड़ का निर्माण करता है, जिसकी जड़ उत्तल पतवार है और एक शीर्ष को हटाकर एक दूसरे के आसपास के बहुभुज के माता-पिता को प्राप्त किया जाता है (बहुभुज के बाहरी हिस्से में [[दो कान प्रमेय]] को लागू करने से यह संभव साबित होता है)। इसके बाद यह बहुभुजों को सूचीबद्ध करने के लिए इस पेड़ पर एक [[रिवर्स-सर्च एल्गोरिदम]] लागू करता है। इस पद्धति के परिणामस्वरूप, सभी बहुभुजीकरणों को [[ई (जटिलता)]] में सूचीबद्ध किया जा सकता है (<math>2^{O(n)}</math> के लिए <math>n</math> अंक) और [[बहुपद स्थान]]।{{r|yahouy}}
+बहुभुज आवरण, कमज़ोर सरल बहुभुज जो प्रत्येक दिए गए बिंदु को एक या अधिक बार शीर्ष के रूप में उपयोग करते हैं, इसमें सभी बहुभुजीकरण शामिल होते हैं और स्थानीय चालों से जुड़े होते हैं।{{r|dfor}} बहुभुजों का एक और अधिक सामान्य वर्ग, आसपास के बहुभुज, सरल बहुभुज होते हैं जिनमें दिए गए कुछ बिंदु शीर्ष के रूप में होते हैं और सभी बिंदुओं को घेरते हैं। वे फिर से स्थानीय रूप से जुड़े हुए हैं, और प्रति बहुभुज बहुपद समय में सूचीबद्ध किए जा सकते हैं। एल्गोरिथ्म बहुभुजों के एक पेड़ का निर्माण करता है, जिसकी जड़ उत्तल संचालन है और एक शीर्ष को हटाकर एक दूसरे के आसपास के बहुभुज के माता-पिता को प्राप्त किया जाता है (बहुभुज के बाहरी हिस्से में [[दो कान प्रमेय]] को लागू करने से यह संभव साबित होता है)। इसके बाद यह बहुभुजों को सूचीबद्ध करने के लिए इस पेड़ पर एक [[रिवर्स-सर्च एल्गोरिदम]] लागू करता है। इस पद्धति के परिणामस्वरूप, सभी बहुभुजीकरणों को [[ई (जटिलता)]] में सूचीबद्ध किया जा सकता है (<math>2^{O(n)}</math> के लिए <math>n</math> अंक) और [[बहुपद स्थान]]।{{r|yahouy}}
 ==अनुप्रयोग==

Anonymous

Search

बहुभुजीकरण: Difference between revisions

Namespaces

More

Page actions

Revision as of 13:12, 4 July 2023

Contents

परिभाषा

अस्तित्व

अनुकूलन

गिनती

पीढ़ी

अनुप्रयोग

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बहुभुजीकरण: Difference between revisions

Revision as of 13:12, 4 July 2023

परिभाषा

अस्तित्व

अनुकूलन

गिनती

पीढ़ी

अनुप्रयोग

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories