فا   |   En
Login
مشاهده‌ مشخصات مقاله

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

Authors
  • محمد رضا رزازي
  • سید محمد ابوالحسنی
Conference دوازدهمین کنفرانس بین‌المللی سالانه انجمن کامپیوتر ایران
Abstract پوش محدب یکی از مرسومترین مسئلههاي هندسه محاسباتی محسوب میشود. الگوریتمهاي مختلفی براي پوش محدب ارائه شده است که از مهمترین آنها میتوان به الگوریتمهاي گراهام، جارویس و پوش سریع اشاره کرد. ما در این مقاله الگوریتمهاي جدی دي براي به دست آوردن پوش محدب ارائه میکنیم. این الگوریتمها با پیش فرض عدد صحیح بودن زاویه خط گذرنده از دو نقطه متوالی پوش محدب (زاویه نسبت به خط افق )، به خوبی عمل میکنند و بدون این پیش فرض جوابی تقریبی میدهند که میتوان ب ا بهین ه سازي این الگوریتمها جوابی بسیار دقیق و نزدیک به جواب نهایی تولید کرد. بهترین الگوریتمی که تاکنون از لحاظ مرتبه زمانی ارائه شده است الگوریتم ادغام قبل از غلبه اس ت ک ه داراي مرتبه زمانی O(n logh ) است h) تعداد نقاط روي پوش محدب است). اما الگوریتم جدید در تمام حالات داراي مرتبه زمانی O(n ) میباشد. هر چند که n داراي ضریب زیادي است؛ الگوریتم ما در صورتی که تعداد نقاط ورودي زیاد باشد سریعتر از الگوریتمه اي قبلی به جواب خواهد رسید.
قیمت
  • برای اعضای سایت : 100,000 Rial
  • برای دانشجویان عضو انجمن : 20,000 Rial
  • برای اعضای عادی انجمن : 40,000 Rial

خرید مقاله