الگوریتمهای تقریبی زمان خطی برای مسئله پوش محدب
Publish place: 12th Annual Conference of Computer Society of Iran
Publish Year: 1385
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 3,440
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI12_378
تاریخ نمایه سازی: 23 دی 1386
Abstract:
پوش محدب یکی از مرسومترین مسئلههای هندسه محاسباتی محسوب میشود. الگوریتمهای مختلفی برای پوش محدب ارائه شده است که از مهمترین آنها میتوان به الگوریتمهای گراهام، جارویس و پوش سریع اشاره کرد. ما در این مقاله الگوریتمهای جدی دی برای به دست آوردن پوش محدب ارائه میکنیم. این الگوریتمها با پیش فرض عدد صحیح بودن زاویه خط گذرنده از دو نقطه متوالی
پوش محدب (زاویه نسبت به خط افق )، به خوبی عمل میکنند و بدون این پیش فرض جوابی تقریبی میدهند که میتوان ب ا بهین ه سازی این الگوریتمها جوابی بسیار دقیق و نزدیک به جواب نهایی تولید کرد.
بهترین الگوریتمی که تاکنون از لحاظ مرتبه زمانی ارائه شده است الگوریتم ادغام قبل از غلبه اس ت ک ه دارای مرتب ه زم انی O(n logh )است h) تعداد نقاط روی پوش محدب است). اما الگوریتم جدید در تمام حالات دارای مرتبه زمانی O(n ) میباشد. هر چند کهn دارای ضریب زیادی است؛ الگوریتم ما در صورتی که تعداد نقاط ورودی زیاد باشد سریعتر از الگوریتمه ای قبلی به جواب خواهد رسید.
Keywords:
Authors
محمدرضا رزازی
عضو هیات علمی دانشگاه، دانشگاه امیرکبیر، دانشکده مهندسی کامپیوتر و
سیدمحمد ابوالحسنی
دانشگاه امیرکبیر، دانشکده مهندسی کامپیوتر و فناوری اطلاعات