الگوریتم های ابتکاری برای شبه مثلث بندی مجموعه نقاط تصادفی در صفحه

پیام:
چکیده:
یافتن الگوریتم هایی برای مسائل متنوع مطرح شده در هندسه محاسباتی از جمله مسئله شبه مثلث بندی مجموعه نقاط در صفحه جزو موضوعات علمی است که تاکنون زمینه فکری دانشمندان علم کامپیوتر را به خود اختصاص داده است. شبه مثلث-بندی S که مجموعه ای از n نقطه در صفحه است، افراز پوسته ی محدب این مجموعه نقاط از طریق اتصال چندین یال به تعدادی شبه مثلث می باشد که همه نقاط را در بر می گیرد. برای شبه مثلث بندی معیارهای بهینگی گوناگونی بررسی شده است که اغلب براساس وزن یال ها و گوشه ها بوده که در آن شبه مثلث بندی مجموعه نقاط با کمترین وزن یال ها جزو مسائل باز می باشد. به طور کلی شبه مثلث بندی کمینه به شبه مثلث بندی اطلاق می شود که تعداد شبه مثلث های ایجاد شده در آن دقیقا n-2 شبه-مثلث و تعداد کمترین یال های مورد نیاز در آن 2n-3 یال باشد، همچنین تمامی رئوس یک شبه مثلث بندی کمینه نوک دار می باشند؛ به این معنی که در بین تمام زوایای وابسته به آن رئوس، یک زاویه ی بزرگ تر از π وجود داشته باشد.
هدف این مقاله ارائه روش هایی جدید برای شبه مثلث بندی مجموعه نقاط S در صفحه است تا بتواند تفکرات الگوریتمی جدیدی را در این زمینه باز کند. این مقاله نشان می دهد که ایجاد لایه هایی از پوسته محدب برای مجموعه نقاط و شبه مثلث بندی آن ها با دو الگوریتم خاص منجر به تولید شبه مثلث بندی کمینه خواهد شد. همچنین الگوریتمی جدید برای ایجاد یک چندضلعی ساده حلزونی شبه مثلث بندی شده ارائه می دهد که تولید چندضلعی های ساده تصادفی در دو زمینه مهم کاربردی، شامل بررسی عملکرد الگوریتم ها و ارزیابی زمان پردازنده مورد نیاز الگوریتم ها، حائز اهمیت می باشد.
زبان:
فارسی
در صفحه:
49
لینک کوتاه:
magiran.com/p1284532 
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یک‌ساله به مبلغ 990,000ريال می‌توانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
  • حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران می‌شود.
  • پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانه‌های چاپی و دیجیتال را به کاربر نمی‌دهد.
دسترسی سراسری کاربران دانشگاه پیام نور!
اعضای هیئت علمی و دانشجویان دانشگاه پیام نور در سراسر کشور، در صورت ثبت نام با ایمیل دانشگاهی، تا پایان فروردین ماه 1403 به مقالات سایت دسترسی خواهند داشت!
In order to view content subscription is required

Personal subscription
Subscribe magiran.com for 50 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!