انجمن کامپیوتر ایران

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