انجمن کامپیوتر ایران

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