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

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