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

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

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

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

علی نورالله – استادیار دانشکده مهندسی برق و کامپیوتر دانشگاه تربیت دبیر شهید رجایی
فهیمه طاهرخانی – دانشجوی کارشناسی ارشد دانشکده مهندسی برق و کامپیوتر دانشگاه آزاد اسل

چکیده:

ابعاد چندضلعی ساده تصادفی و شبه مثلث بندی یک چندضلعی از مسائل مطرح درهندسه محاسباتی محسوب می شوند تولید چندضلعی تصادفی در زمینه بررسی صحت و درستی الگوریتمها مورد استفاده قرار میگیرد دراین مقاله الگوریتمی جدید برای ایجاد یک چندضلعی ساده حلزونی از مجموعه نقاط تصادفی s درصفحه با استفاده از پوسته های محدب لایه ای ارایه شده است که بطور همزمان نیز شبه مثلث بندی روی آن انجام می شود این الگوریتم ابداعی جدید دارای مرتبه زمانی O(nlogn است لذا جزو الگوریتم های بهینه به شمار می آید