سال انتشار: ۱۳۹۰

محل انتشار: هفتمین کنفرانس ماشین بینایی و پردازش تصویر

تعداد صفحات: ۶

نویسنده(ها):

لعیا محمدی – دانشکده مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی قزوین
علی نوراله – دانشکده مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی قزوین و دانشکده م
سمیرا حسینی – دانشکده مهندسی برق و کامپیوتر، دانشگاه آزاد اسلامی قزوین

چکیده:

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