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