ऋजुरेखीय बहुभुज

This article is about समकोण बहुभुज. For यूक्लिड के तत्वों में दी गई परिभाषा, see बहुभुज.

सरल रेखीय बहुभुज के कुछ उदाहरण

ऋजुरेखीय बहुभुज एक बहुभुज है जिसकी सभी बहुभुज भुजाएँ समकोण पर मिलती हैं। इस प्रकार प्रत्येक शीर्ष पर आंतरिक कोण या तो 90° या 270° होता है। ऋजुरेखीय बहुभुज आइसोथेटिक बहुभुज की एक विशेष स्थिति है।

अनेक स्थितियों में एक और परिभाषा उपयुक्त मानी गयी है:

ऋजुरेखीय बहुभुज एक बहुभुज है जिसमें भुजाएँ कार्तीय निर्देशांक के अक्षों के समानांतर होती हैं। बहुभुजों के समुच्चय के बारे में बात करने पर यह अंतर महत्वपूर्ण हो जाता है : बाद की परिभाषा का अर्थ यह होगा कि समुच्चय में सभी बहुभुज की भुजाओं को समान समन्वय अक्षों के साथ संरेखित किया जाता है। दूसरी परिभाषा के ढांचे के भीतर एक आयताकार बहुभुज के क्षैतिज किनारों और ऊर्ध्वाधर किनारों के बारे में बात करना स्वाभाविक है।

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

सरलरेखीय बहुभुजों के वर्ग का महत्व निम्नलिखित के अनुसार प्राप्त किया जाता है।

• वे डिजाइन और निर्माण में अपनी सादगी के कारण एकीकृत सर्किट एकीकृत सर्किट लेआउट में आकृतियों के प्रतिनिधित्व के लिए सुविधाजनक हैं। अनेक निर्मित वस्तुओं का परिणाम लंबकोणीय बहुभुज होता है।
• कम्प्यूटेशनल ज्यामिति में समस्याएं बहुभुज के संदर्भ में बताई गई हैं, जो अक्सर लंबकोणीय बहुभुजों तक सीमित होने पर अधिक कम्प्यूटेशनल जटिलता सिद्धांत की अनुमति देती हैं। लंबकोणीय बहुभुजों के लिए आर्ट गैलरी प्रमेय द्वारा एक उदाहरण प्रदान किया गया है, जो मनमाने बहुभुजों की तुलना में अधिक कुशल गार्ड कवरेज की ओर ले जाता है।

तत्व

आयताकार बहुभुज के दो प्रकार के किनारे होते हैं: क्षैतिज और लंबवत।

X उत्तल कोनों को चिन्हित करता है; O अवतल कोनों को चिह्नित करता है। नीली रेखाएँ नॉब हैं; लाल रेखाएँ एंटी-नॉब्स हैं; पीली रेखाएँ न तो नॉब और न ही एंटी-नॉब्स हैं।

• लेम्मा: क्षैतिज किनारों की संख्या ऊर्ध्वाधर किनारों की संख्या के बराबर होती है (क्योंकि प्रत्येक क्षैतिज किनारे के बाद एक ऊर्ध्वाधर किनारा होता है और इसके विपरीत)।
  • कोरोलरी: लंबकोणीय पॉलीगोन में किनारों की एक समान संख्या होती है।

सरलरेखीय बहुभुज में दो प्रकार के कोने होते हैं: वे कोने जिनमें छोटा कोण (90°) बहुभुज के आंतरिक होता है, उत्तल कहलाते हैं और वे कोने जिनमें बड़ा कोण (270°) आंतरिक होता है, अवतल कहलाते हैं। एक नॉब्स एक किनारा है जिसके दो अंत बिंदु उत्तल कोने होते हैं। एक एंटीकनॉब एक ​​किनारा है जिसके दो अंत बिंदु अवतल कोने होते हैं।

सरल आयताकार बहुभुज

आयताकार बहुभुज जो कि सरल बहुभुज भी है, उसे छिद्र-मुक्त भी कहा जाता है क्योंकि इसमें कोई छिद्र नहीं होता है - केवल एक सतत सीमा होती है। इसके अनेक रोचक गुण हैं:

1. उत्तल किनारों की संख्या अवतल किनारों की संख्या से चार अधिक है। यह देखने के लिए, कल्पना करें कि आप बहुभुज की सीमा को दक्षिणावर्त पार करते हैं (अपने दाहिने हाथ को बहुभुज के अंदर और अपने बाएं हाथ को बहुभुज के बाहर की ओर रखकर)। उत्तल कोने पर, आप 90° दाएं मुड़ते हैं और किसी अवतल कोने पर आप 90° बाएँ मुड़ जाते हैं। अंत में आपको संपूर्ण 360° मुड़ना होगा और उस वास्तविक बिंदु पर वापस आना होगा; इसलिए दाएँ घुमावों की संख्या बाएँ घुमावों की संख्या से 4 अधिक होनी चाहिए।
   • उपप्रमेय: प्रत्येक आयताकार बहुभुज में कम से कम 4 उत्तल किनारे होते हैं।
2. नॉब्स (दो उत्तल किनारों को जोड़ने वाली भुजाएँ) की संख्या एंटीनॉब्स (दो अवतल किनारों को जोड़ने वाली भुजाएँ) की संख्या से चार अधिक है। यह देखने के लिए कि ऐसा क्यों होता है, X को उत्तल किनारों की संख्या और Y को अवतल किनारों की संख्या मान लेते है। पिछले तथ्य से, 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।
   • उपप्रमेय: प्रत्येक सरलरेखीय बहुभुज में कम से कम 4 नॉब्स होती हैं।

एक आयताकार बहुभुज में वर्ग और आयत

बहुभुज के किनारों के समानांतर किनारों के साथ एक आयताकार बहुभुज को परिमित संख्या में वर्गों या आयतों द्वारा आच्छादित किया जा सकता है (बहुभुज आच्छादन देखें)। एक निश्चित आयताकार बहुभुज P में निहित अनेक प्रकार के वर्गों/आयतों में अंतर करना संभव है:

बहुभुज P में एक अधिकतम वर्ग P में एक वर्ग है जो P में किसी अन्य वर्ग में सम्मलित नहीं है। इसी तरह, एक अधिकतम आयत एक आयत है जो P में किसी अन्य आयत में सम्मलित नहीं है।

एक वर्ग s, P में अधिकतम होता है यदि s के आसन्न किनारों की प्रत्येक जोड़ी 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' जुड़ा नहीं है।

• लेम्मा: एक साधारण आयताकार बहुभुज में, एक अधिकतम वर्ग जिसमें एक नॉब्स नहीं होती है, एक विभाजक है। नॉब को समाहित करने वाला वर्ग, विभाजक हो भी सकता है और नहीं भी। विभिन्न विभाजक वर्गों की संख्या अनंत और अगणनीय भी हो सकती है। उदाहरण के लिए, एक आयत में, प्रत्येक अधिकतम वर्ग जो छोटी भुजाओं में से किसी एक को स्पर्श नहीं करता है, एक विभाजक है।

निर्वाहक वर्ग, एक बहुभुज P में एक वर्ग S है जैसे कि S की सीमा और P की सीमा के बीच का प्रतिच्छेदन निरंतर है। एक अधिकतम निर्वाहक हमेशा एक कोने वाला वर्ग होता है। इसके अतिरिक्त, एक अधिकतम निर्वाहक में हमेशा एक नॉब्स होती है। इसलिए निर्वाहको की संख्या हमेशा परिमित होती है और नॉब्स की संख्या से बंधी होती है।

उनमें उपस्थित नॉब्स की संख्या और उनकी आंतरिक संरचना (चित्र देखें) के आधार पर अनेक अलग-अलग प्रकार के निर्वाहक हैं। एक निर्वाहको के बालकनी को इसके बिंदुओं के रूप में परिभाषित किया गया है जो किसी अन्य अधिकतम वर्ग (चित्र देखें) द्वारा आच्छादित नहीं किया गया है।

कोई वर्ग निर्वाहक और विभाजक दोनों नहीं हो सकता। सामान्य बहुभुजों में, ऐसे वर्ग हो सकते हैं जो न तो निर्वाहक और न ही विभाजक हों, लेकिन साधारण बहुभुजों में ऐसा नहीं हो सकता है:

1. एक साधारण आयताकार बहुभुज में, प्रत्येक अधिकतम वर्ग या तो एक विभाजक या एक निर्वाहक होता है। यह आयतों के लिए भी सत्य है: प्रत्येक अधिकतम आयत या तो एक विभाजक या एक निर्वाहक है।
2. एक साधारण आयताकार बहुभुज में जो एक वर्ग नहीं है, कम से कम दो निर्वाहक होते हैं।

साधारण बहुभुज में अधिकतम वर्गों और एक पेड़ में नोड्स के बीच एक रोचक सादृश्य है: एक निर्वाहक पत्ती के नोड के अनुरूप है और एक विभाजक एक आंतरिक नोड के अनुरूप है।

विशेष स्थितियाँ

सबसे सरल आयताकार बहुभुज एक अक्ष-संरेखित आयत है - एक आयत जिसमें 2 भुजाएँ x अक्ष के समानांतर और 2 भुजाएँ y अक्ष के समानांतर होती हैं। यह भी देखें: न्यूनतम सीमा आयत।

गोलिगॉन एक ऋजुरेखीय बहुभुज है जिसकी भुजाओं की लंबाई क्रम से लेने पर, क्रमागत पूर्णांक. होती है।

एक ऋजुरेखीय बहुभुज जो एक आयत नहीं है, कभी भी उत्तल बहुभुज नहीं होता है, लेकिन यह लम्बवत रूप से उत्तल हो सकता है। लम्बवत उत्तल सरलरेखीय बहुभुज देखें .

एक मोनोटोन ऋजुरेखीय बहुभुज एक मोनोटोन बहुभुज है जो आयताकार बहुभुज भी है।

टी-स्क्वायर रोचक गुणों वाले ऋजुरेखीय बहुभुज के अनुक्रम से उत्पन्न एक फ्रैक्टल है।

सामान्यीकरण

• लंबकोणीय बहुभुज - 3D में लंबकोणीय बहुभुजों का प्राकृतिक सामान्यीकरण।
• ऋजुरेखीयता [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"