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

متن کامل مقاله