گراف پدیداری
در هندسهٔ محاسباتی و ناوبری روبات‌ها، گراف پدیداری (به انگلیسی: Visibility Graph) گرافی است شامل نقاطی که از ناحیهٔ منطقهٔ مورد نظر قابل دید است. در واقع هر گره نمایش دهندهٔ مکانی در محیط است و لبهٔ گراف بین دو نقطهٔ مورد نظر، نشان دهندهٔ ارتباط بین آن دو نقطه، یا دیده شدن یکی از نقاط با قرار گرفتن در نقطهٔ دیگر است و هیج مانعی سد راه دیده شدن این دو نقطه از همدیگر نمی‌شود.
کاربردها[ویرایش]
با استفاده از گراف‌های پدیداری می‌توان کمینه فاصله اقلیدسی بین دو نقطهٔ مورد نظر در فضایی شامل موانع چند ضلعی را پیدا کرد. همیشه کمترین فاصله بین دو نقطه خط راست بین آن دو نقطه هست، مگر آنکه مانعی در میان مسیر مورد نظر باشد. در اینصورت گوشهٔ چند ضلعی مورد نظر باید به عنوان یکی از نقاط میانی(راس‌های گراف پدیداری) انتخاب کرد. به اینصورت می‌توان مسئلهٔ مسیر بهینه در فضای اقلیدسی را به مسئلهٔ کوتاه‌ترین مسیر در یک گراف تبدیل کرد. اکنون در اینجا می‌توان مسئله را به قسمت تقسیم کرد: (۱)ساختن گراف پدیداری از روی مسئلهٔ کوتاه‌ترین مسیر در فضای اقلیدسی (۲) حل مسئلهٔ کوتاه‌ترین مسیر مانند الگوریتم دایکسترا در یک گراف. برای مسیر یابی روباتی که دارای اندازه‌ای قابل توجه است، می‌توان مسئله را تعمیم داد. در واقع در این حالت مسیر بهینه نمی‌تواند کاملاً در لبهٔ موانع عبور کند. چون اگر اینطور باشد، روبات با شعاع غیر جزئی با موانع برخورد می‌کند. مسئله را می‌توان به اینصورت حل کرد که موانع را کمی بزرگتر از آنچه هستند در نظر گرفت و سپس مراحل فوق را در این حالت انجام داد. یکی دیگر از کاربردهای گراف پدیداری در بدست آوردن مکان بهینه برای قرار دادن آنتن‌های رادیویی است.
ساختار[ویرایش]
گراف پدیداری یک چندضلعی ساده، گرافی شامل گوشه‌های آن، به عنوان گره‌های آن است. گراف پدیداری چند ضلعی‌های ساده، یک گراف همیلتونی است. چون مرز یک چند ضلعی تشکیل یک دور همیلتونی می‌دهد. این نوع تعریف گراف پدیداری کامل دقیق نیست، بدین مفهوم که هنوز الگوریتمی وجود ندارد که بتواند در زمان چند جمله‌ای از روی یک گراف پدیداری، چند ضلعی (های) متناظر با آن را در صورت وجود بازسازی کند.
مسئله‌های مرتبط[ویرایش]
در مسئلهٔ نگارخانه هنری (هندسه) هدف پیدا کردن مجموعه از نقاط در محیط است، بطوریکه بتوان تمام نقاط در محیط را از روی آن نقاط به‌طور کامل مشاهده کرد. برخی از حالت‌های مسئلهٔ نگارخانه هنری را می‌توان به صورتی معادل از طریق پیدا کردن زیر مجموعهٔ غالب در یک گراف حل کرد. خطوط bitanget مجموعه‌ای از اشکال عبارت است از کلیهٔ خطوطی که حداقل بر دو نقطه از شکل مماس باشند. مجموعهٔ bitangetهای یک مجموعه چند ضلعی، یک گراف پدیداری تشکیل می‌دهند که راس‌های آن شامل گوشه‌های چندضلعی‌ها هستند و داخل چند ضلعی‌ها به عنوان موانع محیط محسوب می‌شوند. یکی از ایده‌ها برای بهینه تر کردن عملکرد گراف‌های پدیداری استفاده از bianget در ساختن آنهاست.
منابع[ویرایش]
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), "Chapter 15: Visibility Graphs", Computational Geometry (2nd ed.), اشپرینگر ساینس+بیزینس مدیا, pp. 307–317, ISBN 3-540-65620-0.
- Lozano-Pérez, Tomás; Wesley, Michael A. (1979), "An algorithm for planning collision-free paths among polyhedral obstacles", Communications of the ACM, 22 (10): 560–570, doi:10٫1145/359156٫359164
{{citation}}: Check|doi=value (help).