Visibility graph
કોમ્પ્યુટેશનલ ભૂમિતિ અને રોબોટ ગતિ આયોજનમાં, દૃશ્યતા આલેખ એ આંતરદૃષ્ટિ સ્થળોનો આલેખ છે, જે સામાન્ય રીતે યુક્લિડિયન સમતલમાં બિંદુઓ અને અવરોધોના સમૂહ માટે છે. આલેખમાં દરેક નોડ બિંદુ સ્થાનનું પ્રતિનિધિત્વ કરે છે, અને દરેક ધાર તેમની વચ્ચેના દૃશ્યમાન જોડાણનું પ્રતિનિધિત્વ કરે છે. એટલે કે, જો બે સ્થાનોને જોડતો રેખા ખંડ કોઈ અવરોધમાંથી પસાર થતો નથી, તો ગ્રાફમાં તેમની વચ્ચે એક ધાર દોરવામાં આવે છે. જ્યારે સ્થાનોનો સમૂહ એક લીટીમાં હોય છે, ત્યારે તેને ક્રમબદ્ધ શ્રેણી તરીકે સમજી શકાય છે. તેથી દૃશ્યતા આલેખ સમય શ્રેણી વિશ્લેષણના ક્ષેત્રમાં વિસ્તૃત કરવામાં આવ્યા છે. એપ્લિકેશન્સ દૃશ્યતા આલેખનો ઉપયોગ સમતલમાં બહુકોણીય અવરોધોના સમૂહ વચ્ચે યુક્લિડિયન ટૂંકા માર્ગો શોધવા માટે થઈ શકે છેઃ બે અવરોધો વચ્ચેનો ટૂંકો માર્ગ અવરોધોના શિરોબિંદુઓ સિવાય સીધી રેખાના ભાગોને અનુસરે છે, જ્યાં તે ફરી શકે છે, તેથી યુક્લિડિયન ટૂંકો માર્ગ એ દૃશ્યતા આલેખમાં ટૂંકો માર્ગ છે જે તેના નોડ્સ તરીકે શરૂઆત અને ગંતવ્ય બિંદુઓ અને અવરોધોની શિરોબિંદુઓ ધરાવે છે. તેથી, યુક્લિડીયન ટૂંકી પાથ સમસ્યાને બે સરળ પેટા સમસ્યાઓમાં વિભાજીત કરી શકાય છેઃ દૃશ્યતા ગ્રાફનું નિર્માણ, અને ગ્રાફમાં ડિજ્ક્સ્ટ્રા અલ્ગોરિધમ જેવા ટૂંકી પાથ અલ્ગોરિધમનો ઉપયોગ કરવો. અવરોધોની સરખામણીમાં બિન-નજીવા કદના રોબોટની ગતિનું આયોજન કરવા માટે, રોબોટના કદની ભરપાઈ કરવા માટે અવરોધોને વિસ્તૃત કર્યા પછી સમાન અભિગમનો ઉપયોગ કરી શકાય છે. 1969માં નિલ્સ નિલ્સન દ્વારા શેકી રોબોટ માટે ગતિ આયોજન પર સંશોધન માટે યુક્લિડિયન ટૂંકા માર્ગો માટે દૃશ્યતા આલેખ પદ્ધતિને શ્રેય આપો, અને રશિયન ગણિતશાસ્ત્રીઓ એમ. બી. ઇગ્નાટયેવ, એફ. એમ. કુલકોવ અને એ. એમ. પોક્રોવ્સ્કી દ્વારા આ પદ્ધતિના 1973ના વર્ણનનો પણ ઉલ્લેખ કરો. વિઝિબિલિટી ગ્રાફનો ઉપયોગ રેડિયો એન્ટેનાના પ્લેસમેન્ટની ગણતરી કરવા માટે અથવા વિઝિબિલિટી ગ્રાફ વિશ્લેષણ દ્વારા આર્કિટેક્ચર અને શહેરી આયોજનમાં ઉપયોગમાં લેવાતા સાધન તરીકે પણ થઈ શકે છે. રેખામાં આવેલા સ્થાનોના સમૂહના દૃશ્યતા આલેખને સમય શ્રેણીના આલેખ-સૈદ્ધાંતિક રજૂઆત તરીકે અર્થઘટન કરી શકાય છે. આ ચોક્કસ કેસ સમય શ્રેણી, ગતિશીલ પ્રણાલીઓ અને આલેખ સિદ્ધાંત વચ્ચે સેતુ બનાવે છે. લાક્ષણિકતા સરળ બહુકોણની દૃશ્યતા આલેખમાં બહુકોણના શિરોબિંદુઓ તેના બિંદુ સ્થાનો તરીકે હોય છે, અને બહુકોણનો બાહ્ય ભાગ એકમાત્ર અવરોધ તરીકે હોય છે. સરળ બહુકોણના દૃશ્યતા આલેખ હેમિલ્ટોનિયન આલેખ હોવા જોઈએઃ બહુકોણની સીમા દૃશ્યતા આલેખમાં હેમિલ્ટોનિયન ચક્ર બનાવે છે. તે જાણીતું છે કે તમામ દૃશ્યતા આલેખ એક સરળ બહુકોણને પ્રેરિત કરતા નથી. જો કે, સરળ બહુકોણના દૃશ્યતા આલેખનું કાર્યક્ષમ અલ્ગોરિધમિક લાક્ષણિકતા અજ્ઞાત રહે છે. આ આલેખ સારી રીતે રચાયેલા આલેખના ઘણા જાણીતા પરિવારોમાં આવતા નથીઃ તેઓ સંપૂર્ણ આલેખ, વર્તુળ આલેખ અથવા કોર્ડલ આલેખ ન પણ હોઈ શકે. આ ઘટનાનો એક અપવાદ એ છે કે સરળ બહુકોણના દૃશ્યતા આલેખ કોપ-વિન આલેખ છે. સંબંધિત સમસ્યાઓ આર્ટ ગેલેરીની સમસ્યા એ બિંદુઓનો એક નાનો સમૂહ શોધવાની સમસ્યા છે જેમ કે આ સમૂહમાંથી અન્ય તમામ બિન-અવરોધ બિંદુઓ દેખાય છે. આર્ટ ગેલેરી સમસ્યાના અમુક સ્વરૂપોને દૃશ્યતા આલેખમાં પ્રભુત્વ ધરાવતા સમૂહને શોધવા તરીકે અર્થઘટન કરી શકાય છે. બહુકોણ અથવા વળાંકની પ્રણાલીના બિટાન્જેન્ટ્સ એ રેખાઓ છે જે તેમાંથી બેને તેમના સંપર્કના બિંદુઓ પર પ્રવેશ્યા વિના સ્પર્શ કરે છે. બહુકોણના સમૂહના બિટાન્જેન્ટ્સ દૃશ્યતા આલેખનો સબસેટ બનાવે છે જેમાં બહુકોણના શિરોબિંદુઓ તેના ગાંઠો તરીકે હોય છે અને બહુકોણ પોતે અવરોધો તરીકે હોય છે. યુક્લિડિયન ટૂંકી માર્ગ સમસ્યા માટે દૃશ્યતા આલેખ અભિગમને તમામ દૃશ્યતા ધારોનો ઉપયોગ કરવાને બદલે બિટાન્જેન્ટ્સમાંથી આલેખ બનાવીને ઝડપી બનાવી શકાય છે, કારણ કે યુક્લિડિયન ટૂંકો માર્ગ ફક્ત બિટાન્જેન્ટ સાથે અવરોધની સીમામાં પ્રવેશ કરી શકે છે અથવા છોડી શકે છે. વિઝિબિલિટી ગ્રાફ એનાલિસિસ ફઝી આર્કિટેક્ચરલ સ્પેસિયલ એનાલિસિસ સ્પેસ સિન્ટેક્સ નોટ્સ રેફરન્સ પણ જુઓ. . બાહ્ય કડીઓ વિઝિલીબીટીઃ ફ્લોટિંગ-પોઇન્ટ વિઝિબિલિટી અલ્ગોરિધમ્સ અને સહાયક ડેટા પ્રકારોની મફત ઓપન સોર્સ સી + + લાઇબ્રેરી. આ સોફ્ટવેરનો ઉપયોગ બહુકોણીય છિદ્રો સાથે બહુકોણીય વાતાવરણના દૃશ્યતા આલેખની ગણતરી કરવા માટે થઈ શકે છે. એક મેટલેબ ઈન્ટરફેસ પણ સામેલ છે. રોબોટ ભૌમિતિક આલેખને નિયંત્રિત કરે છે કોમ્પ્યુટેશનલ ભૂમિતિ