Visibility graph
গণনামূলক জ্যামিতি এবং রোবট গতি পরিকল্পনায়, দৃশ্যমানতা গ্রাফ হল অন্তর্দৃষ্টিযোগ্য অবস্থানগুলির একটি গ্রাফ, সাধারণত ইউক্লিডীয় সমতলে বিন্দু এবং বাধাগুলির একটি সেটের জন্য। গ্রাফের প্রতিটি নোড একটি বিন্দু অবস্থানের প্রতিনিধিত্ব করে এবং প্রতিটি প্রান্ত তাদের মধ্যে একটি দৃশ্যমান সংযোগের প্রতিনিধিত্ব করে। অর্থাৎ, যদি দুটি অবস্থানকে সংযুক্তকারী লাইন সেগমেন্ট কোনও বাধা অতিক্রম না করে, তবে গ্রাফে তাদের মধ্যে একটি প্রান্ত টানা হয়। যখন অবস্থানের সেটটি একটি লাইনে থাকে, তখন এটি একটি ক্রমযুক্ত সিরিজ হিসাবে বোঝা যেতে পারে। দৃশ্যমানতা গ্রাফগুলি তাই সময় সিরিজ বিশ্লেষণের ক্ষেত্রে প্রসারিত করা হয়েছে। অ্যাপ্লিকেশন দৃশ্যমানতা গ্রাফগুলি সমতলে বহুভুজাকার বাধাগুলির একটি সেটের মধ্যে ইউক্লিডীয় সংক্ষিপ্ততম পথগুলি খুঁজে বের করতে ব্যবহার করা যেতে পারেঃ দুটি বাধার মধ্যে সংক্ষিপ্ততম পথটি সরল রেখার অংশগুলি অনুসরণ করে ব্যতীত বাধাগুলির শীর্ষে, যেখানে এটি ঘুরতে পারে, তাই ইউক্লিডীয় সংক্ষিপ্ততম পথটি একটি দৃশ্যমানতা গ্রাফের সংক্ষিপ্ততম পথ যা তার নোড হিসাবে শুরু এবং গন্তব্য পয়েন্ট এবং বাধাগুলির শীর্ষগুলি রয়েছে। অতএব, ইউক্লিডীয় সংক্ষিপ্ততম পথ সমস্যাটিকে দুটি সহজ উপ-সমস্যায় বিভক্ত করা যেতে পারেঃ দৃশ্যমানতা গ্রাফ তৈরি করা এবং গ্রাফে ডিজকস্ট্রার অ্যালগরিদমের মতো একটি সংক্ষিপ্ততম পথ অ্যালগরিদম প্রয়োগ করা। বাধাগুলির তুলনায় নগণ্য আকারের একটি রোবটের গতির পরিকল্পনার জন্য, রোবটের আকারের জন্য ক্ষতিপূরণ দেওয়ার জন্য বাধাগুলি প্রসারিত করার পরে অনুরূপ পদ্ধতি ব্যবহার করা যেতে পারে। 1969 সালে নিলস নিলসন কর্তৃক শাকি রোবটের গতি পরিকল্পনার উপর গবেষণার জন্য ইউক্লিডীয় সংক্ষিপ্ততম পথের জন্য দৃশ্যমানতা গ্রাফ পদ্ধতির কৃতিত্ব দেন এবং 1973 সালে রাশিয়ান গণিতবিদ এম. বি. ইগনাটিয়েভ, এফ. এম. কুলাকভ এবং এ. এম. পোক্রোভস্কির দ্বারা এই পদ্ধতির একটি বিবরণ উদ্ধৃত করেন। দৃশ্যমানতা গ্রাফগুলি রেডিও অ্যান্টেনার স্থাপন গণনা করতে বা দৃশ্যমানতা গ্রাফ বিশ্লেষণের মাধ্যমে স্থাপত্য ও নগর পরিকল্পনার মধ্যে ব্যবহৃত একটি সরঞ্জাম হিসাবেও ব্যবহার করা যেতে পারে। একটি লাইনে অবস্থিত অবস্থানগুলির একটি সেটের দৃশ্যমানতা গ্রাফকে একটি সময় সিরিজের গ্রাফ-তাত্ত্বিক উপস্থাপনা হিসাবে ব্যাখ্যা করা যেতে পারে। এই বিশেষ কেসটি টাইম সিরিজ, ডায়নামিক্যাল সিস্টেম এবং গ্রাফ তত্ত্বের মধ্যে একটি সেতু তৈরি করে। বৈশিষ্ট্য একটি সাধারণ বহুভুজের দৃশ্যমানতা গ্রাফের বিন্দু অবস্থান হিসাবে বহুভুজের শীর্ষগুলি রয়েছে এবং একমাত্র বাধা হিসাবে বহুভুজের বাইরের অংশ রয়েছে। সাধারণ বহুভুজের দৃশ্যমানতা গ্রাফ অবশ্যই হ্যামিল্টনিয়ান গ্রাফ হতে হবেঃ দৃশ্যমানতা গ্রাফে বহুভুজের সীমানা একটি হ্যামিল্টনিয়ান চক্র গঠন করে। এটি জানা যায় যে সমস্ত দৃশ্যমানতা গ্রাফ একটি সাধারণ বহুভুজকে প্ররোচিত করে না। যাইহোক, সাধারণ বহুভুজগুলির দৃশ্যমানতা গ্রাফগুলির একটি দক্ষ অ্যালগরিদমিক বৈশিষ্ট্যকরণ অজানা রয়ে গেছে। এই গ্রাফগুলি সুসংগঠিত গ্রাফের অনেক পরিচিত পরিবারের মধ্যে পড়ে নাঃ এগুলি নিখুঁত গ্রাফ, বৃত্তাকার গ্রাফ বা কর্ডাল গ্রাফ নাও হতে পারে। এই ঘটনার একটি ব্যতিক্রম হল সাধারণ বহুভুজগুলির দৃশ্যমানতা গ্রাফগুলি কপ-উইন গ্রাফ। সম্পর্কিত সমস্যা আর্ট গ্যালারির সমস্যা হল পয়েন্টগুলির একটি ছোট সেট খুঁজে বের করার সমস্যা যাতে এই সেট থেকে অন্যান্য সমস্ত অ-বাধা পয়েন্ট দৃশ্যমান হয়। আর্ট গ্যালারি সমস্যার কিছু রূপকে দৃশ্যমানতার আলেখ্যে একটি প্রভাবশালী সেট খুঁজে পাওয়া হিসাবে ব্যাখ্যা করা যেতে পারে। বহুভুজ বা বক্ররেখার একটি সিস্টেমের বিট্যাঞ্জেন্টগুলি এমন একটি রেখা যা তাদের যোগাযোগের বিন্দুতে প্রবেশ না করে তাদের মধ্যে দুটিকে স্পর্শ করে। বহুভুজের একটি সেটের বিট্যাঞ্জেন্টগুলি দৃশ্যমানতা গ্রাফের একটি উপসেট গঠন করে যার নোড হিসাবে বহুভুজের শীর্ষগুলি এবং বাধা হিসাবে বহুভুজগুলি থাকে। ইউক্লিডীয় সংক্ষিপ্ততম পথ সমস্যার দৃশ্যমানতা গ্রাফ পদ্ধতিকে সমস্ত দৃশ্যমানতা প্রান্ত ব্যবহার করার পরিবর্তে বিট্যাঞ্জেন্টগুলি থেকে একটি গ্রাফ তৈরি করে ত্বরান্বিত করা যেতে পারে, কারণ একটি ইউক্লিডীয় সংক্ষিপ্ততম পথ শুধুমাত্র একটি বিট্যাঞ্জেন্ট বরাবর কোনও প্রতিবন্ধকতার সীমানায় প্রবেশ করতে বা ছেড়ে যেতে পারে। আরও দেখুন দৃশ্যমানতা গ্রাফ বিশ্লেষণ অস্পষ্ট স্থাপত্য স্থানিক বিশ্লেষণ স্পেস সিনট্যাক্স নোটস রেফারেন্স। । বাহ্যিক লিঙ্ক ভিজিলিবিটিঃ ভাসমান-বিন্দু দৃশ্যমানতা অ্যালগরিদম এবং সহায়ক ডেটা প্রকারের একটি মুক্ত উৎস সি + + লাইব্রেরি। এই সফ্টওয়্যারটি বহুভুজ ছিদ্র সহ বহুভুজ পরিবেশের দৃশ্যমানতা গ্রাফ গণনা করার জন্য ব্যবহার করা যেতে পারে। একটি ম্যাটল্যাব ইন্টারফেসও অন্তর্ভুক্ত করা হয়েছে। রোবো জ্যামিতিক গ্রাফ নিয়ন্ত্রণ করে গণনামূলক জ্যামিতি