Visibility graph
कम्प्यूटेशनल ज्यामिति और रोबोट गति योजना में, एक दृश्यता ग्राफ अंतर-दृश्यमान स्थानों का एक ग्राफ है, आमतौर पर यूक्लिडियन तल में बिंदुओं और बाधाओं के एक समूह के लिए। ग्राफ में प्रत्येक नोड एक बिंदु स्थान का प्रतिनिधित्व करता है, और प्रत्येक किनारा उनके बीच एक दृश्य संबंध का प्रतिनिधित्व करता है। अर्थात्, यदि दो स्थानों को जोड़ने वाला रेखा खंड किसी भी बाधा से नहीं गुजरता है, तो ग्राफ में उनके बीच एक किनारा खींचा जाता है। जब स्थानों का समूह एक पंक्ति में होता है, तो इसे एक क्रमबद्ध श्रृंखला के रूप में समझा जा सकता है। इसलिए दृश्यता ग्राफ को समय श्रृंखला विश्लेषण के क्षेत्र में विस्तारित किया गया है। अनुप्रयोग समतल में बहुभुज बाधाओं के एक समूह के बीच यूक्लिडियन सबसे छोटे मार्गों को खोजने के लिए दृश्यता ग्राफ का उपयोग किया जा सकता हैः दो बाधाओं के बीच का सबसे छोटा मार्ग बाधाओं के शीर्षों को छोड़कर सीधी रेखा खंडों का अनुसरण करता है, जहां यह मुड़ सकता है, इसलिए यूक्लिडियन सबसे छोटा मार्ग एक दृश्यता ग्राफ में सबसे छोटा मार्ग है जिसमें इसके नोड्स के रूप में शुरुआत और गंतव्य बिंदु और बाधाओं के शीर्ष होते हैं। इसलिए, यूक्लिडियन सबसे छोटी पथ समस्या को दो सरल उप-समस्याओं में विघटित किया जा सकता हैः दृश्यता ग्राफ का निर्माण, और ग्राफ में डिजक्स्ट्रा के एल्गोरिदम जैसे सबसे छोटे पथ एल्गोरिदम को लागू करना। बाधाओं की तुलना में गैर-नगण्य आकार वाले रोबोट की गति की योजना बनाने के लिए, रोबोट के आकार की भरपाई के लिए बाधाओं को बढ़ाने के बाद एक समान दृष्टिकोण का उपयोग किया जा सकता है। 1969 में नील निल्सन द्वारा शेकी रोबोट के लिए गति योजना पर अनुसंधान के लिए यूक्लिडियन सबसे छोटे मार्गों के लिए दृश्यता ग्राफ विधि को श्रेय दें, और रूसी गणितविदों एम. बी. इग्नाटयेव, एफ. एम. कुलकोव और ए. एम. पोक्रोव्स्की द्वारा इस विधि के 1973 के विवरण का भी हवाला दें। दृश्यता ग्राफ का उपयोग रेडियो एंटेना के स्थान की गणना करने के लिए या दृश्यता ग्राफ विश्लेषण के माध्यम से वास्तुकला और शहरी योजना के भीतर उपयोग किए जाने वाले उपकरण के रूप में भी किया जा सकता है। एक पंक्ति में स्थित स्थानों के एक समूह के दृश्यता ग्राफ की व्याख्या एक समय श्रृंखला के ग्राफ-सैद्धांतिक प्रतिनिधित्व के रूप में की जा सकती है। यह विशेष मामला समय श्रृंखला, गतिशील प्रणालियों और ग्राफ सिद्धांत के बीच एक सेतु बनाता है। एक साधारण बहुभुज के दृश्यता ग्राफ में बहुभुज के शीर्ष उसके बिंदु स्थानों के रूप में होते हैं, और बहुभुज का बाहरी भाग एकमात्र बाधा के रूप में होता है। सरल बहुभुज के दृश्यता ग्राफ हैमिल्टनियन ग्राफ होने चाहिएः बहुभुज की सीमा दृश्यता ग्राफ में हैमिल्टनियन चक्र बनाती है। यह ज्ञात है कि सभी दृश्यता ग्राफ एक साधारण बहुभुज को प्रेरित नहीं करते हैं। हालांकि, सरल बहुभुज के दृश्यता ग्राफ का एक कुशल एल्गोरिथमिक लक्षण वर्णन अज्ञात है। ये ग्राफ अच्छी तरह से संरचित ग्राफ के कई ज्ञात परिवारों में नहीं आते हैंः वे सही ग्राफ, सर्कल ग्राफ या कॉर्डल ग्राफ नहीं हो सकते हैं। इस घटना का एक अपवाद यह है कि सरल बहुभुज के दृश्यता ग्राफ कॉप-विन ग्राफ हैं। संबंधित समस्याएं आर्ट गैलरी की समस्या बिंदुओं के एक छोटे से समूह को खोजने की समस्या है जैसे कि अन्य सभी गैर-बाधा बिंदु इस समूह से दिखाई देते हैं। आर्ट गैलरी समस्या के कुछ रूपों की व्याख्या दृश्यता ग्राफ में एक प्रमुख सेट खोजने के रूप में की जा सकती है। बहुभुज या वक्रों की एक प्रणाली के बिटैंजेंट वे रेखाएँ हैं जो उनमें से दो को उनके संपर्क के बिंदुओं पर प्रवेश किए बिना छूती हैं। बहुभुज के एक समूह के बिटैंजेंट दृश्यता ग्राफ का एक उपसमुच्चय बनाते हैं जिसमें बहुभुज के शीर्ष अपने नोड्स के रूप में होते हैं और बहुभुज स्वयं बाधाओं के रूप में होते हैं। यूक्लिडियन सबसे छोटी पथ समस्या के लिए दृश्यता ग्राफ दृष्टिकोण को सभी दृश्यता किनारों का उपयोग करने के बजाय बिटैंजेंट से एक ग्राफ बनाकर तेज किया जा सकता है, क्योंकि एक यूक्लिडियन सबसे छोटा मार्ग केवल बिटैंजेंट के साथ एक बाधा की सीमा में प्रवेश कर सकता है या छोड़ सकता है। दृश्यता ग्राफ विश्लेषण अस्पष्ट वास्तुशिल्प स्थानिक विश्लेषण अंतरिक्ष वाक्यविन्यास नोट्स संदर्भ भी देखें। .. बाहरी लिंक विजिलाइबिटीः फ्लोटिंग-पॉइंट विजिबिलिटी एल्गोरिदम और सहायक डेटा प्रकारों का एक मुक्त मुक्त स्रोत सी + + पुस्तकालय। इस सॉफ्टवेयर का उपयोग बहुभुज छिद्रों के साथ बहुभुज वातावरण के दृश्यता ग्राफ की गणना के लिए किया जा सकता है। एक मैटलैब इंटरफेस भी शामिल है। यंत्रमानव ज्यामितीय आलेखों को नियंत्रित करता है कम्प्यूटेशनल ज्यामिति