ऋजुरेखीय बहुभुज
एक सीधीरेखीय बहुभुज एक बहुभुज है जिसकी सभी बहुभुज भुजाएँ समकोण पर मिलती हैं। इस प्रकार प्रत्येक शीर्ष पर आंतरिक कोण या तो 90° या 270° होता है। रेक्टिलाइनियर पॉलीगोन आइसोथेटिक बहुभुज का एक विशेष मामला है।
कई मामलों में एक और परिभाषा बेहतर है: एक सीधा बहुभुज एक बहुभुज है जिसमें कार्तीय समन्वय प्रणाली के अक्षों के समानांतर भुजाएँ होती हैं। पॉलीगॉन के सेट के बारे में बात करने पर यह अंतर महत्वपूर्ण हो जाता है: बाद की परिभाषा का अर्थ यह होगा कि सेट में सभी पॉलीगॉन की भुजाओं को समान समन्वय अक्षों के साथ संरेखित किया जाता है। दूसरी परिभाषा के ढांचे के भीतर एक आयताकार बहुभुज के क्षैतिज किनारों और ऊर्ध्वाधर किनारों के बारे में बात करना स्वाभाविक है।
रेक्टिलाइनियर बहुभुजों को ओर्थोगोनल बहुभुज के रूप में भी जाना जाता है। उपयोग में आने वाली अन्य शर्तें आइसो-ओरिएंटेड, अक्ष गठबंधन और एक्सिस-ओरिएंटेड पॉलीगॉन हैं। जब इस प्रकार के बहुभुज आयत होते हैं तो ये विशेषण कम भ्रामक होते हैं, और शब्द अक्ष-संरेखित आयत को प्राथमिकता दी जाती है, हालांकि ऑर्थोगोनल आयत और आयताकार आयत भी उपयोग में हैं।
सरलरेखीय बहुभुजों के वर्ग का महत्व निम्नलिखित से आता है।
- वे डिजाइन और निर्माण के लिए अपनी सादगी के कारण एकीकृत सर्किट एकीकृत सर्किट लेआउट में आकृतियों के प्रतिनिधित्व के लिए सुविधाजनक हैं। कई निर्मित वस्तुओं का परिणाम ऑर्थोगोनल बहुभुज होता है।
- कम्प्यूटेशनल ज्यामिति में समस्याएं बहुभुज के संदर्भ में बताई गई हैं, जो अक्सर ऑर्थोगोनल बहुभुजों तक सीमित होने पर अधिक कम्प्यूटेशनल जटिलता सिद्धांत की अनुमति देती हैं। ऑर्थोगोनल बहुभुजों के लिए आर्ट गैलरी प्रमेय द्वारा एक उदाहरण प्रदान किया गया है, जो मनमाने बहुभुजों की तुलना में अधिक कुशल गार्ड कवरेज की ओर ले जाता है।
तत्व
एक आयताकार बहुभुज के दो प्रकार के किनारे होते हैं: क्षैतिज और लंबवत।
- लेम्मा: क्षैतिज किनारों की संख्या ऊर्ध्वाधर किनारों की संख्या के बराबर होती है (क्योंकि प्रत्येक क्षैतिज किनारे के बाद एक ऊर्ध्वाधर किनारा होता है और इसके विपरीत)।
- कोरोलरी: ऑर्थोगोनल पॉलीगोन में किनारों की एक समान संख्या होती है।
right|285x285px एक सरलरेखीय बहुभुज में दो प्रकार के कोने होते हैं: वे कोने जिनमें छोटा कोण (90°) बहुभुज के आंतरिक होता है, उत्तल कहलाते हैं और वे कोने जिनमें बड़ा कोण (270°) आंतरिक होता है, अवतल कहलाते हैं।[1] एक घुंडी एक किनारा है जिसके दो अंत बिंदु उत्तल कोने होते हैं। एक एंटीकनॉब एक किनारा है जिसके दो अंत बिंदु अवतल कोने होते हैं।[1]
सरल आयताकार बहुभुज
एक आयताकार बहुभुज जो कि सरल बहुभुज भी है, उसे छिद्र-मुक्त भी कहा जाता है क्योंकि इसमें कोई छिद्र नहीं होता है - केवल एक सतत सीमा होती है। इसके कई रोचक गुण हैं:
- उत्तल कोनों की संख्या अवतल कोनों की संख्या से चार अधिक है। यह देखने के लिए, कल्पना करें कि आप बहुभुज की सीमा को दक्षिणावर्त पार करते हैं (अपने दाहिने हाथ को बहुभुज के अंदर और अपने बाएं हाथ को बाहर)। उत्तल कोने पर, आप 90° दाएं मुड़ते हैं; किसी भी अवतल कोने पर आप 90° बाएँ मुड़ जाते हैं। अंत में आपको संपूर्ण 360° मोड़ना होगा और मूल बिंदु पर वापस आना होगा; इसलिए दाएँ घुमावों की संख्या बाएँ घुमावों की संख्या से 4 अधिक होनी चाहिए।
- उपप्रमेय: प्रत्येक आयताकार बहुभुज में कम से कम 4 उत्तल कोने होते हैं।
- घुंडी (दो उत्तल कोनों को जोड़ने वाली भुजाएँ) की संख्या एंटीकनॉब्स (दो अवतल कोनों को जोड़ने वाली भुजाएँ) की संख्या से चार अधिक है। देखने के लिए क्यों, X उत्तल कोनों की संख्या और Y होने दें अवतल कोनों की संख्या। पिछले तथ्य से, एक्स=वाई+4। चलो XX उत्तल कोनों की संख्या के बाद एक उत्तल कोने, XY उत्तल कोनों की संख्या के बाद एक अवतल कोने, YX और YY को समान रूप से परिभाषित करते हैं। फिर जाहिर तौर पर X=XX+XY=XX+YX और Y=XY+YY=YX+YY। इसलिए XX=X-XY=X-(Y-YY)=YY+(X-Y)=YY+4।[2]
- उपप्रमेय: प्रत्येक सरलरेखीय बहुभुज में कम से कम 4 गांठें होती हैं।
एक आयताकार बहुभुज में वर्ग और आयत
बहुभुज के किनारों के समानांतर किनारों के साथ एक आयताकार बहुभुज को परिमित संख्या में वर्गों या आयतों द्वारा कवर किया जा सकता है (बहुभुज कवरिंग देखें)। एक निश्चित आयताकार बहुभुज P में निहित कई प्रकार के वर्गों/आयतों में अंतर करना संभव है:[1]
बहुभुज पी में एक अधिकतम वर्ग पी में एक वर्ग है जो पी में किसी अन्य वर्ग में शामिल नहीं है। इसी तरह, एक अधिकतम आयत एक आयत है जो P में किसी अन्य आयत में समाहित नहीं है।
एक वर्ग s P में अधिकतम होता है यदि s के आसन्न किनारों की प्रत्येक जोड़ी P की सीमा को काटती है। दोनों पक्षों का प्रमाण विरोधाभास से है:
- यदि s में एक निश्चित सन्निकट जोड़ी P की सीमा को नहीं काटती है, तो इस जोड़ी को आगे सीमा की ओर धकेला जाता है, इसलिए s अधिकतम नहीं है।
- यदि पी में एस अधिकतम नहीं है, तो पी में स वाला एक बड़ा वर्ग है; इस बड़े वर्ग के आंतरिक भाग में s के निकटवर्ती किनारों की एक जोड़ी है, इसलिए यह जोड़ी P की सीमा को नहीं काटती है।
पहली दिशा आयतों के लिए भी सही है, अर्थात: यदि एक आयत s अधिकतम है, तो s के आसन्न किनारों की प्रत्येक जोड़ी P की सीमा को काटती है। दूसरी दिशा आवश्यक रूप से सत्य नहीं है: एक आयत P की सीमा को 3 आसन्न पक्षों में भी काट सकता है और फिर भी यह अधिकतम नहीं हो सकता है क्योंकि इसे 4 पक्ष में बढ़ाया जा सकता है।
उपप्रमेय: 'P' में प्रत्येक अधिकतम वर्ग/आयत में कम से कम दो बिंदु होते हैं, दो विपरीत किनारों पर, जो 'P' की सीमा को काटते हैं।
एक कोने का वर्ग एक बहुभुज P में एक अधिकतम वर्ग s है, जैसे कि s का कम से कम एक कोना P के उत्तल कोने को ओवरलैप करता है। प्रत्येक उत्तल कोने के लिए, इसे कवर करने वाला एक अधिकतम (कोना) वर्ग होता है, लेकिन एक अधिकतम वर्ग एक से अधिक कोने को कवर कर सकता है। हर कोने के लिए, इसे कवर करने वाले कई अलग-अलग अधिकतम आयत हो सकते हैं।
एक बहुभुज P में एक विभाजक वर्ग P में एक वर्ग s है जैसे कि P−s' जुड़ा नहीं है।
- लेम्मा: एक साधारण आयताकार बहुभुज में, एक अधिकतम वर्ग जिसमें एक घुंडी नहीं होती है, एक विभाजक है।[3] नॉब वाला वर्ग विभाजक हो भी सकता है और नहीं भी। विभिन्न विभाजक वर्गों की संख्या अनंत और बेशुमार भी हो सकती है। उदाहरण के लिए, एक आयत में, प्रत्येक अधिकतम वर्ग जो छोटी भुजाओं में से किसी एक को स्पर्श नहीं करता है, एक विभाजक है।
एक निरंतर वर्ग एक बहुभुज पी में एक वर्ग एस है जैसे कि एस की सीमा और पी की सीमा के बीच का चौराहा निरंतर है। एक अधिकतम निरंतर हमेशा एक कोने वाला वर्ग होता है। इसके अलावा, एक अधिकतम निरंतरता में हमेशा एक घुंडी होती है। इसलिए निरंतरकों की संख्या हमेशा परिमित होती है और घुंडियों की संख्या से बंधी होती है।
उनमें मौजूद घुंडियों की संख्या और उनकी आंतरिक संरचना (चित्र देखें) के आधार पर कई अलग-अलग प्रकार के निरंतर हैं। एक निरंतरता के बालकनी को इसके बिंदुओं के रूप में परिभाषित किया गया है जो किसी अन्य अधिकतम वर्ग (चित्र देखें) द्वारा कवर नहीं किया गया है।
कोई वर्ग निरंतर और विभाजक दोनों नहीं हो सकता। सामान्य बहुभुजों में, ऐसे वर्ग हो सकते हैं जो न तो निरंतर और न ही विभाजक हों, लेकिन साधारण बहुभुजों में ऐसा नहीं हो सकता है:[1]# एक साधारण आयताकार बहुभुज में, प्रत्येक अधिकतम वर्ग या तो एक विभाजक या एक निरंतर होता है। यह आयतों के लिए भी सत्य है: प्रत्येक अधिकतम आयत या तो एक विभाजक या एक सतत है।
- एक साधारण आयताकार बहुभुज में जो एक वर्ग नहीं है, कम से कम दो निरंतर होते हैं।
एक साधारण बहुभुज में अधिकतम वर्गों और एक पेड़ में नोड्स के बीच एक दिलचस्प सादृश्य है: एक निरंतर पत्ती के नोड के अनुरूप है और एक विभाजक एक आंतरिक नोड के अनुरूप है।
विशेष मामले
सबसे सरल आयताकार बहुभुज एक अक्ष-संरेखित आयत है - एक आयत जिसमें 2 भुजाएँ x अक्ष के समानांतर और 2 भुजाएँ y अक्ष के समानांतर होती हैं। यह भी देखें: न्यूनतम बाउंडिंग आयत।
एक जगहें एक सीधीरेखीय बहुभुज है जिसकी भुजाओं की लंबाई लगातार पूर्णांक होती है।
एक सीधीरेखीय बहुभुज जो एक आयत नहीं है, कभी भी उत्तल बहुभुज नहीं होता है, लेकिन यह लम्बवत रूप से उत्तल हो सकता है। लम्बवत उत्तल सरलरेखीय बहुभुज देखें .
एक मोनोटोन रेक्टिलाइनियर बहुभुज एक मोनोटोन बहुभुज है जो रेक्टिलाइनियर भी है।
एक टी-स्क्वायर (फ्रैक्टल) | टी-स्क्वायर दिलचस्प गुणों वाले रेक्टिलाइनियर पॉलीगोन के अनुक्रम से उत्पन्न एक फ्रैक्टल है।
सामान्यीकरण
- पॉलीहेड्रॉन#ऑर्थोगोनल पॉलीहेड्रा - 3डी में ओर्थोगोनल बहुभुजों का प्राकृतिक सामान्यीकरण।
- सीधीरेखीयता [1]
रेखीय बहुभुजों से संबंधित एल्गोरिथम समस्याएँ
उनमें से अधिकांश को सामान्य बहुभुजों के लिए भी कहा जा सकता है, लेकिन अधिक कुशल एल्गोरिदम की अपेक्षा पर अलग से विचार किया जाना चाहिए
- ऑर्थोगोनल रेंज खोज
- ऑर्थोगोनल उत्तल पतवार निर्माण
- ऑर्थोगोनल बहुभुजों के लिए बहुभुजों पर बूलियन संचालन (उदाहरण के लिए, प्रतिच्छेदन (सेट सिद्धांत) और संघ (सेट सिद्धांत))
- मोशन प्लानिंग / पथ योजना / मार्ग रेक्टिलाइनियर बाधाओं के बीच
- दृश्यता की समस्याएं (रोशनी की समस्याएं)
- रेक्टीलाइनियर आर्ट गैलरी की समस्याएं
- अधिकतम खाली आयत
आयताकार अपघटन
सरलरेखीय बहुभुजों के लिए विशेष रुचि एक दिए गए सरलरेखीय बहुभुज को सरल इकाइयों - आमतौर पर आयतों या वर्गों में विघटित करने की समस्याएं हैं। अपघटन की समस्याएँ कई प्रकार की होती हैं:
- समस्याओं को कवर करने में, लक्ष्य इकाइयों (वर्गों या आयतों) का सबसे छोटा समूह खोजना है, जिसका मिलन बहुभुज के बराबर हो। इकाइयां ओवरलैप हो सकती हैं। बहुभुज आवरण देखें।
- पैकिंग समस्याओं में, लक्ष्य गैर-अतिव्यापी इकाइयों का सबसे बड़ा समूह खोजना है जिसका संघ बहुभुज में समाहित है। संघ बहुभुज से छोटा हो सकता है।
- विभाजन की समस्याओं में, लक्ष्य गैर-अतिव्यापी इकाइयों का सबसे छोटा समूह खोजना है जिसका संघ बहुभुज के बराबर है। बहुभुज विभाजन देखें।
इस पेज में लापता आंतरिक लिंक की सूची
- बहुभुज पक्ष
- एकीकृत परिपथ
- साधारण बहुभुज
- बहुभुज आवरण
- लंबवत रूप से उत्तल
- टी-स्क्वायर (भग्न)
- सरलता
- रेक्टिलाइनियर आर्ट गैलरी समस्या
- चौराहा (सेट सिद्धांत)
संदर्भ
- Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer. ISBN 0-387-96131-3. 1st edition: ; 2nd printing, corrected and expanded, 1988., chapter 8: "The Geometry of Rectangles"
- ↑ 1.0 1.1 1.2 1.3 Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "समान आयतों के साथ सरल बहुभुजों को कवर करने के लिए एक रेखीय-समय एल्गोरिथम". International Journal of Computational Geometry & Applications. 06: 79–102. doi:10.1142/S021819599600006X.
- ↑ "बिट्स के जोड़े की गिनती". Stack Exchange. November 17, 2013.
- ↑ Albertson, M. O.; o’Keefe, C. J. (1981). "क्षेत्रों को वर्गों से आच्छादित करना". SIAM Journal on Algebraic and Discrete Methods. 2 (3): 240. doi:10.1137/0602026.
