الگوریتم هایی بهینه برای تولید چندضلعی های تصادفی مارپیچی و چندبخشی

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

Keywords:

پوسته محدب , چندضلعی ساده تصادفی , قابلیت دید , گرافیک کامپیوتری