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

توليد چند¬ضلعی ساده تصادفی از جمله مسائل مطرح در هندسه محاسباتی می¬باشد. این مساله در بررسی صحت عملکرد الگوریتم¬ها و نیز در زمینه¬های مختلف گرافيک کامپيوتری نظیر خلق تصاویر پدیده¬های طبیعی تصادفی (مانند پدیده ابر¬ و سطح زمین)، به¬طور گسترده¬ای مورد استفاده قرار می¬گیرد. در این مقاله یک الگوریتم جدید برای تولید چندضلعی ساده تصادفی از یک مجموعه¬ نقاط تصادفی واقع بر صفحه ارائه شده است. در این الگوریتم ابتدا لایه¬های محدب نقاط تولید می¬شوند و سپس با¬¬ استفاده از این لایه¬ها و برخی خواص موجود در آن¬ها، یک چند¬ضلعی از نقاط تولید می¬گردد. پیچیدگی زمانی این الگوريتم از مرتبه Ο(nlogn) می¬باشد که نشان می¬دهد این الگوریتم از نظر زمانی در وضعیت بهینه قرار دارد. از آنجا که زمان اجرا در برخی از کاربرد¬های بلادرنگ نظیر بازی¬های رایانه¬ای از اهمیت بالایی برخوردار است، این الگوریتم می¬تواند در این¬گونه موارد بسیار مفید واقع شود.