گراف پدیداری

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در هندسهٔ محاسباتی و ناوبری روبات‌ها، گراف پدیداری (به انگلیسی: Visibility Graph) گرافی است شامل نقاطی که از ناحیهٔ منطقهٔ مورد نظر قابل دید است. در واقع هر گره نمایش دهندهٔ مکانی در محیط است و لبهٔ گراف بین دو نقطهٔ مورد نظر، نشان دهندهٔ ارتباط بین آن دو نقطه، یا دیده شدن یکی از نقاط با قرار گرفتن در نقطهٔ دیگر است و هیج مانعی سد راه دیده شدن این دو نقطه از همدیگر نمی‌شود.

کاربردها[ویرایش]

با استفاده از گراف‌های پدیداری می‌توان کمینه فاصله اقلیدسی بین دو نقطهٔ مورد نظر در فضایی شامل موانع چند ضلعی را پیدا کرد. همیشه کمترین فاصله بین دو نقطه خط راست بین آن دو نقطه هست، مگر آنکه مانعی در میان مسیر مورد نظر باشد. در اینصورت گوشهٔ چند ضلعی مورد نظر باید به عنوان یکی از نقاط میانی(راس‌های گراف پدیداری) انتخاب کرد. به اینصورت می‌توان مسالهٔ مسیر بهینه در فضای اقلیدسی را به مسالهٔ کوتاه ترین مسیر در یک گراف تبدیل کرد. اکنون در اینجا می‌توان مساله را به قسمت تقسیم کرد: (۱)ساختن گراف پدیداری از روی مسالهٔ کوتاه ترین مسیر در فضای اقلیدسی (۲) حل مسالهٔ کوتاه ترین مسیر مانند الگوریتم دایکسترا در یک گراف. برای مسیر یابی روباتی که دارای اندازه‌ای قابل ناجزئی است، می‌توان مساله را تعمیم داد. در واقع در این حالت مسیر بهینه نمی‌تواند کاملا در لبهٔ موانع عبور کند. چون اگر اینطور باشد، روبات با شعاع غیر جزئی با موانع برخورد می‌کند. مساله را می‌توان به اینصورت حل کرد که موانع را کمی بزرگتر از آنچه هستند در نظر گرفت و سپس مراحل فوق را در این حالت انجام داد. یکی دیگر از کاربردهای گراف پدیداری در بدست آوردن مکان بهینه برای قرار دادن آنتن‌های رادیویی است.

ساختار[ویرایش]

گراف پدیداری یک چندضعلی ساده، گرافی شامل گوشه‌های آن، به عنوان گره‌های آن است. گراف پدیداری چند ضلعی‌های ساده، یک گراف همیلتونی است. چون مرز یک چند ضلعی تشکیل یک دور همیلتونی می‌دهد. این نوع تعرفی گراف پدیداری کامل دقیق نیست، بدین مفهمون که هنوز الگوریتمی وجود ندارد که بتواند در زمان چند جمله‌ای از روی یک گراف پدیداری، چند ضلعی (های) متناظر با آن را در صورت وجود بازسازی کند.

مساله‌های مرتبط[ویرایش]

در مسالهٔ نگارخانه_هنری_(هندسه) هدف پیداکردن مجموعه از نقاط در محیط است، بطوریکه بتوان تمام نقاط در محیط را از روی آن نقاط به طور کامل مشاهده کرد. برخی از حالت‌های مسالهٔ نگارخانه هنری را می‌توان به صورتی معادل از طریق پیداکردن زیر مجموعهٔ غالب در یک گراف حل کرد. خطوط bitanget مجموعه‌ای از اشکال عبارت است از کلیهٔ خطوطی که حداقل بر دو نقطه از شکل مماس باشند. مجموعهٔ bitangetهای یک مجموعه چند ضلعی، یک گراف پدیداری تشکیل می‌دهند که راس‌های آن شامل گوشه‌های چندضلعی‌ها هستند و داخل چند ضلعی‌ها به عنوان موانع محیط محسوب می‌شوند. یکی از ایده‌ها برای بهینه تر کردن عملکر گراف‌های پدیداری استفاده از bianget در ساختن آنهاست.

منابع[ویرایش]

پیوند به بیرون[ویرایش]

جستارهای وابسته[ویرایش]