This is a good article. Click here for more information.

बहुभुजीकरण

From Vigyanwiki

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

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

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

परिभाषा

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

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

अस्तित्व

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

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

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

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

अनुकूलन

Unsolved problem in mathematics:

What is the computational complexity of the longest polygonalization?

(more unsolved problems in mathematics)

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

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

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

गणना

Unsolved problem in mathematics:

What is the computational complexity of counting polygonalizations?

(more unsolved problems in mathematics)

किसी दिए गए बिंदु सेट के सभी बहुभुजों की गणना की समस्या #P से संबंधित है, जो एनपी में निर्णय समस्याओं से जुड़ी गणना की समस्याओं का वर्ग है। हालाँकि, यह अज्ञात है कि यह #पी-पूर्ण है या नहीं, यदि नहीं, तो इसकी कम्प्यूटेशनल जटिलता क्या हो सकती है।[23][24] बिंदुओं के समूह में बिल्कुल बहुभुजीकरण होता है यदि और केवल यदि यह उत्तल स्थिति में हो।[1] वहाँ बिंदुओं के सेट उपस्थित हैं जिनके लिए बहुभुजीकरण की संख्या जितनी बड़ी है,[25] और बिंदुओं के प्रत्येक सेट में अधिकतम बहुभुजीकरण हैं।[6]

बिंदुओं के लेबल वाले त्रिकोणों पर तलीय विभाजक प्रमेय को प्रयुक्त करने के तरीकों का उपयोग उपघातांकीय समय, में बिंदुओं के सेट के सभी बहुभुजीकरणों को गिनने के लिए किया जा सकता है।[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]

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

अनुप्रयोग

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

यह भी देखें

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

संदर्भ

  1. ↑ Jump up to: 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. ↑ Jump up to: 2.0 2.1 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. ↑ Jump up to: 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. ↑ Jump up to: 4.0 4.1 Grünbaum, Branko (1994), "Hamiltonian polygons and polyhedra" (PDF), Geombinatorics, 3 (3): 83–89, MR 1326479
  5. ↑ Jump up to: 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. ↑ Jump up to: 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. ↑ Jump up to: 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
  8. ↑ Malkevitch, Joseph (2016), "Are Precise Definitions a Good Idea?", AMS Feature Column, American Mathematical Society
  9. ↑ Jump up to: 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
  10. ↑ Steinhaus, Hugo (1964), One Hundred Problems in Elementary Mathematics, Basic Books, pp. 17, 85–86, ISBN 9780486811802
  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
  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
  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
  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
  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
  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
  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
  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.
  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
  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
  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
  22. ↑ 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
  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
  24. ↑ O'Rourke, Joseph (January 1, 2003), "Problem 16: Simple Polygonalizations", The Open Problems Project
  25. ↑ García, Alfredo; Noy, Marc; Tejel, Javier (2000), "Lower bounds on the number of crossing-free subgraphs of ", Computational Geometry: Theory & Applications, 16 (4): 211–221, doi:10.1016/S0925-7721(00)00010-9, MR 1775294
  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
  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
  28. ↑ Jump up to: 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
  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
  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
  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
  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
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बहुभुजीकरण&oldid=216241’