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

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

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

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

محمدرضا رزازی – عضو هیأت علمی دانشگاه، دانشگاه امیرکبیر، دانشکده مهندسی کامپیوتر و
سیدمحمد ابوالحسنی – دانشگاه امیرکبیر، دانشکده مهندسی کامپیوتر و فناوری اطلاعات

چکیده:

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