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

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

پوش محدب، الگوریتم تقریبی، هندسه محاسباتی