स्यूडोट्राएंगल

छद्म त्रिकोण तीन चिकनी उत्तल सेट (बाएं), और बहुभुज छद्म त्रिकोण (दाएं) के बीच।

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

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

यहां चर्चा की गई अधिकांश सामग्री के विस्तृत सर्वेक्षण के लिए, रोते, फ्रांसिस्को सैंटोस लील और इलियाना स्ट्रेइनु (2008) देखें।

छद्म त्रिकोण

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

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

किसी छद्म त्रिभुज का उत्तल पतवार त्रिभुज होता है। उत्तल शिखरों की प्रत्येक जोड़ी के बीच स्यूडोट्राएंगल सीमा के साथ घटता या तो त्रिभुज के भीतर होता है या इसके किनारों में से के साथ मेल खाता है।

स्यूडोट्राएंगुलेशन

स्यूडोट्राएंगुलेशन प्लेन के एक क्षेत्र का स्यूडोट्राएंगल में विभाजन है। समतल के किसी क्षेत्र का कोई भी त्रिभुज (ज्यामिति) स्यूडोट्राएंगुलेशन है। जबकि एक ही क्षेत्र के किन्हीं भी दो त्रिकोणों में किनारों और त्रिकोणों की संख्या समान होनी चाहिए, वही स्यूडोट्रायंगुलेशन के लिए सही नहीं है; उदाहरण के लिए, यदि क्षेत्र स्वयं n-शीर्ष बहुभुज स्यूडोट्राएंगल है, तो इसके स्यूडोट्राएंग्यूलेशन में कम से कम स्यूडोट्राएंगल और n किनारे हो सकते हैं, या जितने n - 2 स्यूडोट्राएंगल्स और 2एन - 3 किनारे हैं।

न्यूनतम स्यूडोट्राएंगुलेशन स्यूडोट्राएंगुलेशन T है, जैसे कि T का कोई उपग्राफ विमान के समान उत्तल क्षेत्र को आवरण करने वाला स्यूडोट्राएंगुलेशन नहीं है। n शीर्षों के साथ न्यूनतम स्यूडोट्राएंग्युलेशन में कम से कम 2n - 3 किनारे होने चाहिए; यदि इसमें बिल्कुल 2n - 3 किनारे हैं, तो यह नुकीला स्यूडोट्राएंगुलेशन होना चाहिए, किन्तु 3n - O(1) किनारों के साथ न्यूनतम स्यूडोट्राएंगुलेशन उपस्तिथ हैं।

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

गुडमुंडसन ​​एट अल (2004) न्यूनतम कुल किनारे की लंबाई के साथ बिंदु सेट या बहुभुज के स्यूडोट्रायंगुलेशन को खोजने की समस्या पर विचार करें और इस समस्या के लिए सन्निकटन एल्गोरिदम प्रदान करें।

नुकीला स्यूडोट्राएंगुलेशन

इस क्रम से प्राप्त प्लानर बिंदु सेट और नुकीले स्यूडोट्राएंगुलेशन का गोलाबारी क्रम।

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

v शीर्षों के साथ नुकीले स्यूडोट्राएंगुलेशन में बिल्कुल 2v - 3 किनारे होने चाहिए। इसके बाद साधारण दोहरी गिनती (सबूत तकनीक) तर्क होता है जिसमें यूलर विशेषता सम्मलित होती है: जैसा कि प्रत्येक चेहरा किन्तु बाहरी छद्म त्रिकोण है, तीन उत्तल कोणों के साथ, छद्म त्रिकोणासन में आसन्न किनारों के बीच 3f - 3 उत्तल कोण होने चाहिए। प्रत्येक किनारा दो कोणों के लिए दक्षिणावर्त किनारा है, इसलिए कुल 2e कोण हैं, जिनमें से v को छोड़कर सभी उत्तल हैं। इस प्रकार, 3f − 3 = 2e − v। इसे यूलर समीकरण f − e + v = 2 के साथ जोड़कर और परिणामी समकालिक रैखिक समीकरणों को हल करने पर e = 2v − 3 मिलता है। इसी तर्क से यह भी पता चलता है कि f = v − 1 (सहित) उत्तल पतवार चेहरों में से के रूप में), इसलिए स्यूडोट्राएंगुलेशन में बिल्कुल v - 2 स्यूडोट्राएंगल होना चाहिए।

इसी तरह, चूंकि किसी नुकीले स्यूडोट्राएंगुलेशन के किसी भी k-वर्टेक्स उपग्राफ को इसके लंबरूप के नुकीला स्यूडोट्राएंगुलेशन बनाने के लिए पूरा किया जा सकता है, इसलिए उपग्राफ में अधिकतम 2k - 3 किनारे होने चाहिए। इस प्रकार, नुकीले स्यूडोट्रायंगुलेशन लमान ग्राफ को परिभाषित करने वाली स्थितियाँ को पूरा करते हैं: उनके पास बिल्कुल 2v - 3 किनारे होते हैं, और उनके k-शीर्ष उपग्राफ में अधिकतम 2k - 3 किनारे होते हैं। लैमन ग्राफ़, और इसलिए सूडोट्रायंगुलेशन भी इंगित करते हैं, दो आयामों में न्यूनतम कठोर ग्राफ़ हैं। प्रत्येक प्लानर लैमन ग्राफ को नुकीले स्यूडोट्रायंगुलेशन के रूप में खींचा जा सकता है, चूंकि प्लानर लैमन ग्राफ का हर प्लेनर चित्रकारी स्यूडोट्रायंगुलेशन नहीं है। नुकीले स्यूडोट्राएंगुलेशन को खोजने का दूसरा तरीका बिंदु सेट को खोलना है; यानी उत्तल पतवार के शीर्षों को - करके तब तक हटाना जब तक कि सभी बिंदुओं को हटा नहीं दिया जाता। इस प्रकार से बनने वाले निष्कासन के अनुक्रमों का परिवार बिंदु सेट का एंटीमैट्रोइड है, और इस निष्कासन प्रक्रिया द्वारा गठित बिंदु सेटों के अनुक्रम के उत्तल पतवारों के किनारों का सेट स्यूडोट्रायंगुलेशन बनाता है।चूंकि, सभी नुकीले स्यूडोट्राएंग्यूलेशन इस प्रकार से नहीं बन सकते हैं।

आइचोल्ज़र एट अल। (2004) दिखाते हैं कि n बिंदुओं का सेट, जिनमें से h सेट के उत्तल पतवार से संबंधित है, में कम से कम C होना चाहिए_h−2×3^n−h अलग-अलग नुकीले स्यूडोट्राएंगुलेशन, जहां C_iith कैटलन संख्या को दर्शाता है। परिणाम के रूप में, वे दिखाते हैं कि सबसे कम नुकीले स्यूडोट्रायंगुलेशन वाले बिंदु सेट उत्तल बहुभुजों के शीर्ष सेट हैं। आइचोल्ज़र एट अल। (2006) बड़ी संख्या में नुकीले स्यूडोट्रायंगुलेशन के साथ बिंदु सेट की जाँच करें। कम्प्यूटेशनल ज्योमेट्री शोधकर्ताओं ने प्रति स्यूडोट्राएंगुलेशन के लिए थोड़े समय में बिंदु सेट के सभी नुकीला स्यूडोट्राएंग्यूलेशन को सूचीबद्ध करने के लिए एल्गोरिदम भी प्रदान किया है।

यह भी देखें

• डेल्टॉइड वक्र
• वृत्ताकार त्रिकोण

संदर्भ

• Agarwal, Pankaj K.; Basch, Julien; Guibas, Leonidas J.; Hershberger, John; Zhang, Li (2002), "Deformable free-space tilings for kinetic collision detection", International Journal of Robotics Research, 21 (3): 179–197, doi:10.1177/027836402320556395, S2CID 11907465.
• Aichholzer, Oswin; Aurenhammer, Franz; Krasser, Hannes; Speckmann, Bettina (2004), "Convexity minimizes pseudo-triangulations", Computational Geometry Theory and Applications, 28 (1): 3–10, doi:10.1016/j.comgeo.2004.01.002, MR 2070708. Preliminary version in Canad. Conf. Comput. Geom., 2002.
• Aichholzer, Oswin; Orden, David; Santos, Francisco; Speckmann, Bettina (2008), "On the number of pseudo-triangulations of certain point sets", Journal of Combinatorial Theory, Series A, 115 (2): 254–278, arXiv:math/0601747, doi:10.1016/j.jcta.2007.06.002, MR 2382515, S2CID 1189243
• Bereg, Sergey (2005), "Enumerating pseudo-triangulations in the plane", Computational Geometry Theory and Applications, 30 (3): 207–222, doi:10.1016/j.comgeo.2004.09.002, MR 2123970.
• Brönnimann, Hervé; Kettner, Lutz; Pocchiola, Michel; Snoeyink, Jack (2006), "Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm", SIAM Journal on Computing, 36 (3): 721–739, doi:10.1137/050631008, MR 2263009.
• Gudmundsson, Joachim; Levcopoulos, Christos; Kamal, Lodaya; Meena, Mahajan (2004), "Minimum weight pseudo-triangulations" (PDF), in Lodaya, Kamal; Mahajan, Meena (eds.), FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 3328, Springer-Verlag, pp. 299–310, arXiv:0705.3888, doi:10.1007/b104325, ISBN 978-3-540-24058-7, S2CID 47024821.
• Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), "Planar minimally rigid graphs and pseudo-triangulations", Computational Geometry Theory and Applications, 31 (1–2): 31–61, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003, MR 2131802, S2CID 38637747.
• Har-Peled, Sariel (2002), A comment on pseudo-triangulation in three dimensions, archived from the original on 2006-09-12, retrieved 2007-04-12.
• Pocchiola, Michel; Vegter, Gert (1996a), "The visibility complex", International Journal of Computational Geometry and Applications, 6 (3): 297–308, doi:10.1142/S0218195996000204, archived from the original on 2006-12-03. Preliminary version in Ninth ACM Symp. Computational Geometry (1993) 328–337.
• Pocchiola, Michel; Vegter, Gert (1996b), "Topologically sweeping visibility complexes via pseudotriangulations", Discrete and Computational Geometry, 16 (4): 419–453, doi:10.1007/BF02712876, MR 1414964.
• Pocchiola, Michel; Vegter, Gert (1996c), "Pseudo-triangulations: theory and applications", Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pp. 291–300, doi:10.1145/237218.237398, S2CID 15948239.
• Rote, Günter; Santos, Francisco; Streinu, Ileana (2003), "Expansive motions and the polytope of pointed pseudo-triangulations", Discrete and Computational Geometry — The Goodman–Pollack Festschrift, Springer-Verlag, pp. 699–736, arXiv:math.CO/0206027, doi:10.1007/978-3-642-55566-4_33, S2CID 14689476.
• Rote, Günter; Santos, Francisco; Streinu, Ileana (2008), "Pseudo-triangulations — a survey", Surveys on discrete and computational geometry, Contemporary Mathematics, vol. 453, Providence, RI: American Mathematical Society, pp. 343–410, MR 2405689.
• Rote, Günter; Wang, Cao An; Wang, Lusheng; Xu, Yinfeng (2003), "On constrained minimum pseudotriangulations" (PDF), Computing and Combinatorics, Lecture Notes in Computer Science, vol. 2697, Springer-Verlag, pp. 445–454.
• Speckmann, Bettina; Tóth, Csaba D. (2005), "Allocating vertex π-Guards in simple polygons via pseudo-triangulations", Discrete and Computational Geometry, 33 (2): 345–364, doi:10.1007/s00454-004-1091-9, MR 2121300.
• Streinu, Ileana (2000), "A combinatorial approach to planar non-colliding robot arm motion planning", Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 443–453, doi:10.1109/SFCS.2000.892132, S2CID 9420124.
• Streinu, Ileana (2005), "Pseudo-triangulations, rigidity and motion planning", Discrete and Computational Geometry, 34 (4): 587–635, doi:10.1007/s00454-005-1184-0, MR 2173930.
• Streinu, Ileana (2006), "Parallel-redrawing mechanisms, pseudo-triangulations and kinetic planar graphs", Proc. Int. Symp. Graph Drawing (GD 2005), Springer-Verlag, Lecture Notes in Computer Science 3843, pp. 421–433.