स्यूडोट्राएंगल: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:Pseudotriangles.svg|thumb|upright=1.4|छद्म त्रिकोण तीन चिकनी उत्तल सेट (बाएं), और | [[File:Pseudotriangles.svg|thumb|upright=1.4|छद्म त्रिकोण तीन चिकनी उत्तल सेट (बाएं), और बहुभुज छद्म त्रिकोण (दाएं) के बीच।]][[यूक्लिडियन ज्यामिति]] में, स्यूडोट्राएंगल (''छद्म-त्रि[[कोण]]'') विमान (ज्यामिति) का सरल रूप से जुड़ा उपसमुच्चय है जो किसी भी तीन परस्पर स्पर्शरेखा [[उत्तल सेट]]ों के बीच स्थित होता है। स्यूडोट्रायंगुलेशन (''छद्म-त्रिकोण'') विमान के क्षेत्र का स्यूडोट्राएंगल्स में विभाजन है, और नुकीला स्यूडोट्रायंगुलेशन स्यूडोट्राएंगुलेशन है जिसमें प्रत्येक शीर्ष पर घटना के किनारे π से कम के कोण को फैलाते हैं। | ||
यद्यपि स्यूडोट्राएंगल और स्यूडोट्राएंग्यूलेशन शब्द गणित में बहुत लंबे समय से विभिन्न अर्थों के साथ प्रयोग किए जाते रहे हैं,<ref>For "pseudo-triangle" see, e.g., | यद्यपि स्यूडोट्राएंगल और स्यूडोट्राएंग्यूलेशन शब्द गणित में बहुत लंबे समय से विभिन्न अर्थों के साथ प्रयोग किए जाते रहे हैं,<ref>For "pseudo-triangle" see, e.g., | ||
| Line 23: | Line 23: | ||
| issue = 1 | | issue = 1 | ||
| pages = 14–17 | | pages = 14–17 | ||
| mr = 0447029}}.</ref> विमान में उत्तल बाधाओं के बीच दृश्यता संबंधों और स्पर्शरेखाओं की गणना के संबंध में 1993 में मिशेल पॉचिओला और गर्ट वेगर द्वारा यहां उपयोग की जाने वाली शर्तों को पेश किया गया था। [[इलियाना स्ट्रेनु]] (2000, 2005) ने बढ़ई के शासक की समस्या के समाधान के हिस्से के रूप में सबसे पहले पॉइन्टेड स्यूडोट्रायंगुलेशन पर विचार किया था, यह | | mr = 0447029}}.</ref> विमान में उत्तल बाधाओं के बीच दृश्यता संबंधों और स्पर्शरेखाओं की गणना के संबंध में 1993 में मिशेल पॉचिओला और गर्ट वेगर द्वारा यहां उपयोग की जाने वाली शर्तों को पेश किया गया था। [[इलियाना स्ट्रेनु]] (2000, 2005) ने बढ़ई के शासक की समस्या के समाधान के हिस्से के रूप में सबसे पहले पॉइन्टेड स्यूडोट्रायंगुलेशन पर विचार किया था, यह प्रमाण है कि विमान में किसी भी [[सरल बहुभुज पथ]] को निरंतर गति के क्रम से सीधा किया जा सकता है। गतिमान वस्तुओं के बीच टकराव का पता लगाने के लिए स्यूडोट्रायंगुलेशन का भी उपयोग किया गया है<ref>Agarwal et al. (2002).</ref> और डायनेमिक ग्राफ ड्राइंग और शेप मॉर्फिंग के लिए।<ref>Streinu (2006).</ref> [[कठोरता सिद्धांत (संरचनात्मक)]] में कम से कम कठोर [[ प्लेनर ग्राफ |प्लेनर ग्राफ]] के उदाहरण के रूप में नुकीले स्यूडोट्रायंगुलेशन उत्पन्न होते हैं,<ref>Haas et al. (2005)</ref> और [[आर्ट गैलरी प्रमेय]] के संबंध में गार्ड रखने के तरीकों में।<ref>Speckmann and Tóth (2005).</ref> प्लानर पॉइंट सेट का [[antimatroid]] नुकीले स्यूडोट्रायंगुलेशन को जन्म देता है,<ref name="Har-Peled 2002">Har-Peled (2002).</ref> हालाँकि सभी नुकीले स्यूडोट्रायंगुलेशन इस तरह से उत्पन्न नहीं हो सकते हैं। | ||
यहां चर्चा की गई अधिकांश सामग्री के विस्तृत सर्वेक्षण के लिए, रोते, [[फ्रांसिस्को सैंटोस लील]] और इलियाना स्ट्रेइनु (2008) देखें। | यहां चर्चा की गई अधिकांश सामग्री के विस्तृत सर्वेक्षण के लिए, रोते, [[फ्रांसिस्को सैंटोस लील]] और इलियाना स्ट्रेइनु (2008) देखें। | ||
| Line 29: | Line 29: | ||
== छद्म [[त्रिकोण]] == | == छद्म [[त्रिकोण]] == | ||
Pocchiola और Vegter (1996a,b,c) ने मूल रूप से | Pocchiola और Vegter (1996a,b,c) ने मूल रूप से स्यूडोट्राएंगल को तीन चिकने उत्तल वक्रों से घिरे हुए विमान के सरल-जुड़े क्षेत्र के रूप में परिभाषित किया जो उनके अंतिम बिंदुओं पर स्पर्शरेखा हैं। हालांकि, बाद के काम व्यापक परिभाषा पर बस गए हैं जो आमतौर पर [[बहुभुज]]ों के साथ-साथ चिकने वक्रों से घिरे क्षेत्रों पर भी लागू होते हैं, और जो तीन शीर्षों पर शून्येतर कोणों की अनुमति देता है। इस व्यापक परिभाषा में, स्यूडोट्राएंगल विमान का सरल रूप से जुड़ा हुआ क्षेत्र है, जिसमें तीन उत्तल कोने होते हैं। इन तीन शीर्षों को जोड़ने वाली तीन सीमाएँ उत्तल होनी चाहिए, इस अर्थ में कि ही सीमा वक्र पर दो बिंदुओं को जोड़ने वाला कोई भी रेखा खंड पूरी तरह से बाहर या छद्म त्रिभुज की सीमा पर होना चाहिए। इस प्रकार, स्यूडोट्राएंगल इन तीन वक्रों के उत्तल पतवारों के बीच का क्षेत्र है, और आम तौर पर कोई भी तीन परस्पर स्पर्शरेखा उत्तल सेट स्यूडोट्राएंगल बनाते हैं जो उनके बीच स्थित होता है। | ||
एल्गोरिथम अनुप्रयोगों के लिए यह विशेष रुचि है कि स्यूडोट्राएंगल्स को चित्रित किया जाए जो कि बहुभुज हैं। | एल्गोरिथम अनुप्रयोगों के लिए यह विशेष रुचि है कि स्यूडोट्राएंगल्स को चित्रित किया जाए जो कि बहुभुज हैं। बहुभुज में, शीर्ष उत्तल होता है यदि यह π से कम के आंतरिक कोण को फैलाता है, और अन्यथा अवतल होता है (विशेष रूप से, हम बिल्कुल π के कोण को अवतल मानते हैं)। किसी भी बहुभुज में कम से कम तीन उत्तल कोण होने चाहिए, क्योंकि बहुभुज का कुल बाहरी कोण 2π है, उत्तल कोण इस कुल में π से कम योगदान करते हैं, और अवतल कोण शून्य या ऋणात्मक मात्रा में योगदान करते हैं। बहुभुज छद्म त्रिभुज बहुभुज है जिसमें ठीक तीन उत्तल शीर्ष होते हैं। विशेष रूप से, कोई भी त्रिभुज, और कोई भी गैर उत्तल चतुर्भुज, छद्म त्रिभुज है। | ||
किसी छद्म त्रिभुज का उत्तल पतवार त्रिभुज होता है। उत्तल शिखरों की प्रत्येक जोड़ी के बीच स्यूडोट्राएंगल सीमा के साथ घटता या तो त्रिभुज के भीतर होता है या इसके किनारों में से | किसी छद्म त्रिभुज का उत्तल पतवार त्रिभुज होता है। उत्तल शिखरों की प्रत्येक जोड़ी के बीच स्यूडोट्राएंगल सीमा के साथ घटता या तो त्रिभुज के भीतर होता है या इसके किनारों में से के साथ मेल खाता है। | ||
== स्यूडोट्राएंगुलेशन == | == स्यूडोट्राएंगुलेशन == | ||
स्यूडोट्राएंगुलेशन प्लेन के | स्यूडोट्राएंगुलेशन प्लेन के क्षेत्र का स्यूडोट्राएंगल में विभाजन है। समतल के किसी क्षेत्र का कोई भी त्रिभुज (ज्यामिति) स्यूडोट्राएंगुलेशन है। जबकि ही क्षेत्र के किन्हीं भी दो त्रिकोणों में किनारों और त्रिकोणों की संख्या समान होनी चाहिए, वही स्यूडोट्रायंगुलेशन के लिए सही नहीं है; उदाहरण के लिए, यदि क्षेत्र स्वयं ''n''-शीर्ष बहुभुज स्यूडोट्राएंगल है, तो इसके स्यूडोट्राएंग्यूलेशन में कम से कम स्यूडोट्राएंगल और ''n'' किनारे हो सकते हैं, या जितने ''n'' - 2 स्यूडोट्राएंगल्स और 2''एन'' - 3 किनारे। | ||
''न्यूनतम स्यूडोट्राएंगुलेशन'' स्यूडोट्राएंगुलेशन ''टी'' है, जैसे कि ''टी'' का कोई सबग्राफ विमान के समान उत्तल क्षेत्र को कवर करने वाला स्यूडोट्राएंगुलेशन नहीं है। ''n'' शीर्षों के साथ न्यूनतम स्यूडोट्राएंग्युलेशन में कम से कम 2''n'' - 3 किनारे होने चाहिए; यदि इसमें बिल्कुल 2''n'' - 3 किनारे हैं, तो यह नुकीला स्यूडोट्राएंगुलेशन होना चाहिए, लेकिन 3''n'' - O(1) किनारों के साथ न्यूनतम स्यूडोट्राएंगुलेशन मौजूद हैं।<ref>Rote, Wang, Wang, and Xu (2003), Theorem 4 and Figure 4.</ref> | |||
अग्रवाल एट अल। (2002) मूविंग पॉइंट्स या मूविंग पॉलीगॉन के स्यूडोट्रायंगुलेशन को बनाए रखने के लिए डेटा संरचनाओं का वर्णन करता है। वे दिखाते हैं कि त्रिकोणासन के स्थान पर स्यूडोट्राएंगुलेशन का उपयोग करने से उनके एल्गोरिदम इन संरचनाओं को अपेक्षाकृत कम दहनशील परिवर्तनों के साथ बनाए रखने की अनुमति देते हैं क्योंकि इनपुट चलते हैं, और वे गतिमान वस्तुओं के बीच टक्कर का पता लगाने के लिए इन गतिशील स्यूडोट्रायंगुलेशन का उपयोग करते हैं। | अग्रवाल एट अल। (2002) मूविंग पॉइंट्स या मूविंग पॉलीगॉन के स्यूडोट्रायंगुलेशन को बनाए रखने के लिए डेटा संरचनाओं का वर्णन करता है। वे दिखाते हैं कि त्रिकोणासन के स्थान पर स्यूडोट्राएंगुलेशन का उपयोग करने से उनके एल्गोरिदम इन संरचनाओं को अपेक्षाकृत कम दहनशील परिवर्तनों के साथ बनाए रखने की अनुमति देते हैं क्योंकि इनपुट चलते हैं, और वे गतिमान वस्तुओं के बीच टक्कर का पता लगाने के लिए इन गतिशील स्यूडोट्रायंगुलेशन का उपयोग करते हैं। | ||
गुडमुंडसन एट अल। (2004) न्यूनतम कुल किनारे की लंबाई के साथ | गुडमुंडसन एट अल। (2004) न्यूनतम कुल किनारे की लंबाई के साथ बिंदु सेट या बहुभुज के स्यूडोट्रायंगुलेशन को खोजने की समस्या पर विचार करें, और इस समस्या के लिए सन्निकटन एल्गोरिदम प्रदान करें। | ||
== पॉइंटेड स्यूडोट्राएंगुलेशन == | == पॉइंटेड स्यूडोट्राएंगुलेशन == | ||
[[File:Convex shelling.svg|thumb|upright=1.4|इस क्रम से प्राप्त | [[File:Convex shelling.svg|thumb|upright=1.4|इस क्रम से प्राप्त प्लानर बिंदु सेट और नुकीले स्यूडोट्राएंगुलेशन का गोलाबारी क्रम।]]नुकीले स्यूडोट्राएंगुलेशन को लाइन सेगमेंट के परिमित गैर-क्रॉसिंग संग्रह के रूप में परिभाषित किया जा सकता है, जैसे कि प्रत्येक शीर्ष पर घटना रेखा खंड अधिकतम π के कोण को फैलाते हैं, और ऐसा कि संरक्षित करते समय किसी भी दो मौजूदा वर्टिकल के बीच कोई लाइन सेगमेंट नहीं जोड़ा जा सकता है। यह संपत्ति। यह देखना कठिन नहीं है कि नुकीला स्यूडोट्रायंगुलेशन इसके उत्तल पतवार का स्यूडोट्रायंगुलेशन है: कोण-फैले गुण को संरक्षित करते हुए सभी उत्तल पतवार किनारों को जोड़ा जा सकता है, और सभी आंतरिक चेहरों को स्यूडोट्राएंगल्स होना चाहिए, अन्यथा दो के बीच द्विस्पर्श रेखा खंड जोड़ा जा सकता है। चेहरे के कोने। | ||
''v'' शीर्षों के साथ | ''v'' शीर्षों के साथ नुकीले स्यूडोट्राएंगुलेशन में बिल्कुल 2''v'' - 3 किनारे होने चाहिए।<ref>First shown by Streinu (2000), but the argument we give here is from Haas et al. (2005), Lemma 5.</ref> इसके बाद साधारण [[ दोहरी गिनती (सबूत तकनीक) |दोहरी गिनती (सबूत तकनीक)]] तर्क होता है जिसमें [[यूलर विशेषता]] शामिल होती है: जैसा कि प्रत्येक चेहरा लेकिन बाहरी छद्म त्रिकोण है, तीन उत्तल कोणों के साथ, छद्म त्रिकोणासन में आसन्न किनारों के बीच 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 किनारे होते हैं। लैमन ग्राफ़, और इसलिए सूडोट्रायंगुलेशन भी इंगित करते हैं, दो आयामों में न्यूनतम कठोर ग्राफ़ हैं। प्रत्येक प्लानर लैमन ग्राफ को | इसी तरह, चूंकि किसी नुकीले स्यूडोट्राएंगुलेशन के किसी भी k-वर्टेक्स सबग्राफ को इसके वर्टिकल के पॉइंटेड स्यूडोट्राएंगुलेशन बनाने के लिए पूरा किया जा सकता है, इसलिए सबग्राफ में अधिकतम 2k - 3 किनारे होने चाहिए। इस प्रकार, नुकीले स्यूडोट्रायंगुलेशन [[लमान ग्राफ]] को परिभाषित करने वाली शर्तों को पूरा करते हैं: उनके पास बिल्कुल 2v - 3 किनारे होते हैं, और उनके k-शीर्ष उपग्राफ में अधिकतम 2k - 3 किनारे होते हैं। लैमन ग्राफ़, और इसलिए सूडोट्रायंगुलेशन भी इंगित करते हैं, दो आयामों में न्यूनतम कठोर ग्राफ़ हैं। प्रत्येक प्लानर लैमन ग्राफ को नुकीले स्यूडोट्रायंगुलेशन के रूप में खींचा जा सकता है, हालांकि प्लानर लैमन ग्राफ का हर प्लेनर ड्राइंग स्यूडोट्रायंगुलेशन नहीं है।<ref>Haas et al. (2005).</ref> | ||
नुकीले स्यूडोट्राएंगुलेशन को खोजने का दूसरा तरीका | नुकीले स्यूडोट्राएंगुलेशन को खोजने का दूसरा तरीका बिंदु सेट को खोलना है; यानी उत्तल पतवार के शीर्षों को - करके तब तक हटाना जब तक कि सभी बिंदुओं को हटा नहीं दिया जाता। इस तरह से बनने वाले निष्कासन के अनुक्रमों का परिवार बिंदु सेट का एंटीमैट्रोइड है, और इस निष्कासन प्रक्रिया द्वारा गठित बिंदु सेटों के अनुक्रम के उत्तल पतवारों के किनारों का सेट स्यूडोट्रायंगुलेशन बनाता है।<ref name="Har-Peled 2002"/>हालांकि, सभी नुकीले स्यूडोट्राएंग्यूलेशन इस तरह से नहीं बन सकते हैं। | ||
आइचोल्ज़र एट अल। (2004) दिखाते हैं कि n बिंदुओं का | आइचोल्ज़र एट अल। (2004) दिखाते हैं कि n बिंदुओं का सेट, जिनमें से h सेट के उत्तल पतवार से संबंधित है, में कम से कम C होना चाहिए<sub>''h''−2</sub>×3<sup>n−h</sup> अलग-अलग नुकीले स्यूडोट्राएंगुलेशन, जहां C<sub>i</sub>ith [[कैटलन संख्या]] को दर्शाता है। परिणाम के रूप में, वे दिखाते हैं कि सबसे कम नुकीले स्यूडोट्रायंगुलेशन वाले बिंदु सेट उत्तल बहुभुजों के शीर्ष सेट हैं। आइचोल्ज़र एट अल। (2006) बड़ी संख्या में नुकीले स्यूडोट्रायंगुलेशन के साथ बिंदु सेट की जाँच करें। कम्प्यूटेशनल ज्योमेट्री शोधकर्ताओं ने प्रति स्यूडोट्राएंगुलेशन के लिए थोड़े समय में बिंदु सेट के सभी पॉइंटेड स्यूडोट्राएंग्यूलेशन को सूचीबद्ध करने के लिए एल्गोरिदम भी प्रदान किया है।<ref>Bereg (2005); Brönnimann et al. (2006).</ref> | ||
Revision as of 20:56, 11 May 2023
यूक्लिडियन ज्यामिति में, स्यूडोट्राएंगल (छद्म-त्रिकोण) विमान (ज्यामिति) का सरल रूप से जुड़ा उपसमुच्चय है जो किसी भी तीन परस्पर स्पर्शरेखा उत्तल सेटों के बीच स्थित होता है। स्यूडोट्रायंगुलेशन (छद्म-त्रिकोण) विमान के क्षेत्र का स्यूडोट्राएंगल्स में विभाजन है, और नुकीला स्यूडोट्रायंगुलेशन स्यूडोट्राएंगुलेशन है जिसमें प्रत्येक शीर्ष पर घटना के किनारे π से कम के कोण को फैलाते हैं।
यद्यपि स्यूडोट्राएंगल और स्यूडोट्राएंग्यूलेशन शब्द गणित में बहुत लंबे समय से विभिन्न अर्थों के साथ प्रयोग किए जाते रहे हैं,[1] विमान में उत्तल बाधाओं के बीच दृश्यता संबंधों और स्पर्शरेखाओं की गणना के संबंध में 1993 में मिशेल पॉचिओला और गर्ट वेगर द्वारा यहां उपयोग की जाने वाली शर्तों को पेश किया गया था। इलियाना स्ट्रेनु (2000, 2005) ने बढ़ई के शासक की समस्या के समाधान के हिस्से के रूप में सबसे पहले पॉइन्टेड स्यूडोट्रायंगुलेशन पर विचार किया था, यह प्रमाण है कि विमान में किसी भी सरल बहुभुज पथ को निरंतर गति के क्रम से सीधा किया जा सकता है। गतिमान वस्तुओं के बीच टकराव का पता लगाने के लिए स्यूडोट्रायंगुलेशन का भी उपयोग किया गया है[2] और डायनेमिक ग्राफ ड्राइंग और शेप मॉर्फिंग के लिए।[3] कठोरता सिद्धांत (संरचनात्मक) में कम से कम कठोर प्लेनर ग्राफ के उदाहरण के रूप में नुकीले स्यूडोट्रायंगुलेशन उत्पन्न होते हैं,[4] और आर्ट गैलरी प्रमेय के संबंध में गार्ड रखने के तरीकों में।[5] प्लानर पॉइंट सेट का antimatroid नुकीले स्यूडोट्रायंगुलेशन को जन्म देता है,[6] हालाँकि सभी नुकीले स्यूडोट्रायंगुलेशन इस तरह से उत्पन्न नहीं हो सकते हैं।
यहां चर्चा की गई अधिकांश सामग्री के विस्तृत सर्वेक्षण के लिए, रोते, फ्रांसिस्को सैंटोस लील और इलियाना स्ट्रेइनु (2008) देखें।
छद्म त्रिकोण
Pocchiola और Vegter (1996a,b,c) ने मूल रूप से स्यूडोट्राएंगल को तीन चिकने उत्तल वक्रों से घिरे हुए विमान के सरल-जुड़े क्षेत्र के रूप में परिभाषित किया जो उनके अंतिम बिंदुओं पर स्पर्शरेखा हैं। हालांकि, बाद के काम व्यापक परिभाषा पर बस गए हैं जो आमतौर पर बहुभुजों के साथ-साथ चिकने वक्रों से घिरे क्षेत्रों पर भी लागू होते हैं, और जो तीन शीर्षों पर शून्येतर कोणों की अनुमति देता है। इस व्यापक परिभाषा में, स्यूडोट्राएंगल विमान का सरल रूप से जुड़ा हुआ क्षेत्र है, जिसमें तीन उत्तल कोने होते हैं। इन तीन शीर्षों को जोड़ने वाली तीन सीमाएँ उत्तल होनी चाहिए, इस अर्थ में कि ही सीमा वक्र पर दो बिंदुओं को जोड़ने वाला कोई भी रेखा खंड पूरी तरह से बाहर या छद्म त्रिभुज की सीमा पर होना चाहिए। इस प्रकार, स्यूडोट्राएंगल इन तीन वक्रों के उत्तल पतवारों के बीच का क्षेत्र है, और आम तौर पर कोई भी तीन परस्पर स्पर्शरेखा उत्तल सेट स्यूडोट्राएंगल बनाते हैं जो उनके बीच स्थित होता है।
एल्गोरिथम अनुप्रयोगों के लिए यह विशेष रुचि है कि स्यूडोट्राएंगल्स को चित्रित किया जाए जो कि बहुभुज हैं। बहुभुज में, शीर्ष उत्तल होता है यदि यह π से कम के आंतरिक कोण को फैलाता है, और अन्यथा अवतल होता है (विशेष रूप से, हम बिल्कुल π के कोण को अवतल मानते हैं)। किसी भी बहुभुज में कम से कम तीन उत्तल कोण होने चाहिए, क्योंकि बहुभुज का कुल बाहरी कोण 2π है, उत्तल कोण इस कुल में π से कम योगदान करते हैं, और अवतल कोण शून्य या ऋणात्मक मात्रा में योगदान करते हैं। बहुभुज छद्म त्रिभुज बहुभुज है जिसमें ठीक तीन उत्तल शीर्ष होते हैं। विशेष रूप से, कोई भी त्रिभुज, और कोई भी गैर उत्तल चतुर्भुज, छद्म त्रिभुज है।
किसी छद्म त्रिभुज का उत्तल पतवार त्रिभुज होता है। उत्तल शिखरों की प्रत्येक जोड़ी के बीच स्यूडोट्राएंगल सीमा के साथ घटता या तो त्रिभुज के भीतर होता है या इसके किनारों में से के साथ मेल खाता है।
स्यूडोट्राएंगुलेशन
स्यूडोट्राएंगुलेशन प्लेन के क्षेत्र का स्यूडोट्राएंगल में विभाजन है। समतल के किसी क्षेत्र का कोई भी त्रिभुज (ज्यामिति) स्यूडोट्राएंगुलेशन है। जबकि ही क्षेत्र के किन्हीं भी दो त्रिकोणों में किनारों और त्रिकोणों की संख्या समान होनी चाहिए, वही स्यूडोट्रायंगुलेशन के लिए सही नहीं है; उदाहरण के लिए, यदि क्षेत्र स्वयं n-शीर्ष बहुभुज स्यूडोट्राएंगल है, तो इसके स्यूडोट्राएंग्यूलेशन में कम से कम स्यूडोट्राएंगल और n किनारे हो सकते हैं, या जितने n - 2 स्यूडोट्राएंगल्स और 2एन - 3 किनारे।
न्यूनतम स्यूडोट्राएंगुलेशन स्यूडोट्राएंगुलेशन टी है, जैसे कि टी का कोई सबग्राफ विमान के समान उत्तल क्षेत्र को कवर करने वाला स्यूडोट्राएंगुलेशन नहीं है। n शीर्षों के साथ न्यूनतम स्यूडोट्राएंग्युलेशन में कम से कम 2n - 3 किनारे होने चाहिए; यदि इसमें बिल्कुल 2n - 3 किनारे हैं, तो यह नुकीला स्यूडोट्राएंगुलेशन होना चाहिए, लेकिन 3n - O(1) किनारों के साथ न्यूनतम स्यूडोट्राएंगुलेशन मौजूद हैं।[7] अग्रवाल एट अल। (2002) मूविंग पॉइंट्स या मूविंग पॉलीगॉन के स्यूडोट्रायंगुलेशन को बनाए रखने के लिए डेटा संरचनाओं का वर्णन करता है। वे दिखाते हैं कि त्रिकोणासन के स्थान पर स्यूडोट्राएंगुलेशन का उपयोग करने से उनके एल्गोरिदम इन संरचनाओं को अपेक्षाकृत कम दहनशील परिवर्तनों के साथ बनाए रखने की अनुमति देते हैं क्योंकि इनपुट चलते हैं, और वे गतिमान वस्तुओं के बीच टक्कर का पता लगाने के लिए इन गतिशील स्यूडोट्रायंगुलेशन का उपयोग करते हैं।
गुडमुंडसन एट अल। (2004) न्यूनतम कुल किनारे की लंबाई के साथ बिंदु सेट या बहुभुज के स्यूडोट्रायंगुलेशन को खोजने की समस्या पर विचार करें, और इस समस्या के लिए सन्निकटन एल्गोरिदम प्रदान करें।
पॉइंटेड स्यूडोट्राएंगुलेशन
नुकीले स्यूडोट्राएंगुलेशन को लाइन सेगमेंट के परिमित गैर-क्रॉसिंग संग्रह के रूप में परिभाषित किया जा सकता है, जैसे कि प्रत्येक शीर्ष पर घटना रेखा खंड अधिकतम π के कोण को फैलाते हैं, और ऐसा कि संरक्षित करते समय किसी भी दो मौजूदा वर्टिकल के बीच कोई लाइन सेगमेंट नहीं जोड़ा जा सकता है। यह संपत्ति। यह देखना कठिन नहीं है कि नुकीला स्यूडोट्रायंगुलेशन इसके उत्तल पतवार का स्यूडोट्रायंगुलेशन है: कोण-फैले गुण को संरक्षित करते हुए सभी उत्तल पतवार किनारों को जोड़ा जा सकता है, और सभी आंतरिक चेहरों को स्यूडोट्राएंगल्स होना चाहिए, अन्यथा दो के बीच द्विस्पर्श रेखा खंड जोड़ा जा सकता है। चेहरे के कोने।
v शीर्षों के साथ नुकीले स्यूडोट्राएंगुलेशन में बिल्कुल 2v - 3 किनारे होने चाहिए।[8] इसके बाद साधारण दोहरी गिनती (सबूत तकनीक) तर्क होता है जिसमें यूलर विशेषता शामिल होती है: जैसा कि प्रत्येक चेहरा लेकिन बाहरी छद्म त्रिकोण है, तीन उत्तल कोणों के साथ, छद्म त्रिकोणासन में आसन्न किनारों के बीच 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 किनारे होते हैं। लैमन ग्राफ़, और इसलिए सूडोट्रायंगुलेशन भी इंगित करते हैं, दो आयामों में न्यूनतम कठोर ग्राफ़ हैं। प्रत्येक प्लानर लैमन ग्राफ को नुकीले स्यूडोट्रायंगुलेशन के रूप में खींचा जा सकता है, हालांकि प्लानर लैमन ग्राफ का हर प्लेनर ड्राइंग स्यूडोट्रायंगुलेशन नहीं है।[9] नुकीले स्यूडोट्राएंगुलेशन को खोजने का दूसरा तरीका बिंदु सेट को खोलना है; यानी उत्तल पतवार के शीर्षों को - करके तब तक हटाना जब तक कि सभी बिंदुओं को हटा नहीं दिया जाता। इस तरह से बनने वाले निष्कासन के अनुक्रमों का परिवार बिंदु सेट का एंटीमैट्रोइड है, और इस निष्कासन प्रक्रिया द्वारा गठित बिंदु सेटों के अनुक्रम के उत्तल पतवारों के किनारों का सेट स्यूडोट्रायंगुलेशन बनाता है।[6]हालांकि, सभी नुकीले स्यूडोट्राएंग्यूलेशन इस तरह से नहीं बन सकते हैं।
आइचोल्ज़र एट अल। (2004) दिखाते हैं कि n बिंदुओं का सेट, जिनमें से h सेट के उत्तल पतवार से संबंधित है, में कम से कम C होना चाहिएh−2×3n−h अलग-अलग नुकीले स्यूडोट्राएंगुलेशन, जहां Ciith कैटलन संख्या को दर्शाता है। परिणाम के रूप में, वे दिखाते हैं कि सबसे कम नुकीले स्यूडोट्रायंगुलेशन वाले बिंदु सेट उत्तल बहुभुजों के शीर्ष सेट हैं। आइचोल्ज़र एट अल। (2006) बड़ी संख्या में नुकीले स्यूडोट्रायंगुलेशन के साथ बिंदु सेट की जाँच करें। कम्प्यूटेशनल ज्योमेट्री शोधकर्ताओं ने प्रति स्यूडोट्राएंगुलेशन के लिए थोड़े समय में बिंदु सेट के सभी पॉइंटेड स्यूडोट्राएंग्यूलेशन को सूचीबद्ध करने के लिए एल्गोरिदम भी प्रदान किया है।[10]
यह भी देखें
- डेल्टॉइड वक्र
- वृत्ताकार त्रिकोण
टिप्पणियाँ
- ↑ For "pseudo-triangle" see, e.g.,
Whitehead, J. H. C. (1961), "Manifolds with transverse fields in Euclidean space", Annals of Mathematics, 73 (1): 154–212, doi:10.2307/1970286, JSTOR 1970286, MR 0124917.
On page 196 this paper refers to a "pseudo-triangle condition" in functional approximation. For "pseudo-triangulation" see, e.g., Belaga, È. G. (1976), "[Heawood vectors of pseudotriangulations]", Doklady Akademii Nauk SSSR (in Russian), 231 (1): 14–17, MR 0447029
{{citation}}: CS1 maint: unrecognized language (link). - ↑ Agarwal et al. (2002).
- ↑ Streinu (2006).
- ↑ Haas et al. (2005)
- ↑ Speckmann and Tóth (2005).
- ↑ 6.0 6.1 Har-Peled (2002).
- ↑ Rote, Wang, Wang, and Xu (2003), Theorem 4 and Figure 4.
- ↑ First shown by Streinu (2000), but the argument we give here is from Haas et al. (2005), Lemma 5.
- ↑ Haas et al. (2005).
- ↑ Bereg (2005); Brönnimann et al. (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.
