الگوریتمهای تقریبی زمان خطی برای مسئله پوش محدب

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

کلیدواژه ها:

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