مشاهده مشخصات مقاله
يک الگوريتم تقريبي براي ساده‌سازي سرزمين
|
نویسنده (ها) |
|
|
مربوط به کنفرانس |
شانزدهمین کنفرانس ملی سالانه انجمن کامپیوتر ایران |
|
چکیده |
در اين مقاله، يک الگوريتم تقريبي براي ساده‌سازي سرزمين مطرح شده است. هدف مسئله ساده‌سازي اين است که، تعدادي از نقاط يک سرزمين حذف شود به نحوي که خطاي سرزمين پس از ساده‌سازي، بيشتر از ميزان تعيين‌شده، نباشد. خطاي ساده‌سازي به دو صورت تعريف مي‌شود، يکي اينکه پس از ساده‌سازي،m نقطه با حداقل خطا در سرزمين وجود داشته باشد يا اينکه، حداکثر خطا پس از ساده‌سازي به ازاي کمترين تعداد نقاط، ϵ باشد. اين مسئله در حوزه‌ي مسائل ان‌پي - سخت قرار دارد.
در اين راستا، ما يک الگوريتم تقريبي براي ساده‌سازي سرزمين بيان کرده‌ايم که، يک سرزمين با n نقطه در فضاي سه بعدي و حداکثر خطاي ϵ>0 را دريافت مي‌کند و در خروجي يک سرزمين ساده‌شده با سايز O(k logk ) در زمان O(n^7 ) حاصل مي‌شود، که k سايز بهينه‌ي سرزمين ساده‌شده به ازاي تقريب - ϵ مي‌باشد.
|
|
قیمت |
-
برای اعضای سایت : ۱٠٠,٠٠٠ ریال
-
برای دانشجویان عضو انجمن : ۲٠,٠٠٠ ریال
-
برای اعضای عادی انجمن : ۴٠,٠٠٠ ریال
|
خرید مقاله
|
|
.gif){kind=icon}