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

يک الگوريتم تقريبي براي ساده‌سازي سرزمين

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

خرید مقاله