الگوریتم های ابتکاری برای شبه مثلث بندی مجموعه نقاط تصادفی در صفحه
- سال انتشار: 1398
- محل انتشار: دوفصلنامه فناوری اطلاعات و ارتباطات ایران، دوره: 5، شماره: 16
- کد COI اختصاصی: JR_AICTI-5-16_001
- زبان مقاله: فارسی
- تعداد مشاهده: 31
نویسندگان
دانشگاه آزاد اسلامی
چکیده
یافتن الگوریتم هایی برای مسائل متنوع مطرح شده در هندسه محاسباتی از جمله مسئله شبه مثلث بندی مجموعه نقاط در صفحه جزو موضوعات علمی است که تاکنون زمینه فکری دانشمندان علم کامپیوتر را به خود اختصاص داده است. شبه مثلث بندی S که مجموعه-ای از n نقطه در صفحه است، افراز پوسته ی محدب این مجموعه نقاط از طریق اتصال چندین یال به تعدادی شبه مثلث می باشد که همه نقاط را در بر می گیرد. برای شبه مثلث بندی معیارهای بهینگی گوناگونی بررسی شده است که اغلب براساس وزن یال ها و گوشه ها بوده که در آن شبه مثلث بندی مجموعه نقاط با کمترین وزن یال ها جزو مسائل باز می باشد. به طور کلی شبه مثلث بندی کمینه به شبه مثلث بندی اطلاق می شود که تعداد شبه مثلث های ایجاد شده در آن دقیقا n-۲ شبه-مثلث و تعداد کمترین یال های مورد نیاز در آن ۲n-۳ یال باشد، همچنین تمامی رئوس یک شبه مثلث بندی کمینه نوک دار می باشند؛ به این معنی که در بین تمام زوایای وابسته به آن رئوس، یک زاویه ی بزرگ تر از π وجود داشته باشد. هدف این مقاله ارائه روش هایی جدید برای شبه مثلث بندی مجموعه نقاط S در صفحه است تا بتواند تفکرات الگوریتمی جدیدی را در این زمینه باز کند. این مقاله نشان می دهد که ایجاد لایه هایی از پوسته محدب برای مجموعه نقاط و شبه مثلث بندی آن ها با دو الگوریتم خاص منجر به تولید شبه مثلث بندی کمینه خواهد شد. همچنین الگوریتمی جدید برای ایجاد یک چندضلعی ساده حلزونی شبه مثلث بندی شده ارائه می دهد که تولید چندضلعی های ساده تصادفی در دو زمینه مهم کاربردی، شامل بررسی عملکرد الگوریتم ها و ارزیابی زمان پردازنده مورد نیاز الگوریتم ها، حائز اهمیت می باشد.کلیدواژه ها
شبه مثلث بندیاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.