انجمن کامپیوتر ایران

برای عضویت کلیک کنید

مشاهده‌ مشخصات مقاله

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

فهیمه دباغی

نویسنده (ها)

شانزدهمین کنفرانس ملی سالانه انجمن کامپیوتر ایران ‫

مربوط به کنفرانس

در اين مقاله، يک الگوريتم تقريبي براي ساده‌سازي سرزمين مطرح شده است. هدف مسئله ساده‌سازي اين است که، تعدادي از نقاط يک سرزمين حذف شود به نحوي که خطاي سرزمين پس از ساده‌سازي، بيشتر از ميزان تعيين‌شده، نباشد. خطاي ساده‌سازي به دو صورت تعريف مي‌شود، يکي اينکه پس از ساده‌سازي،m نقطه با حداقل خطا در سرزمين وجود داشته باشد يا اينکه، حداکثر خطا پس از ساده‌سازي به ازاي کمترين تعداد نقاط، ϵ باشد. اين مسئله در حوزه‌ي مسائل ان‌پي - سخت قرار دارد. در اين راستا، ما يک الگوريتم تقريبي براي ساده‌سازي سرزمين بيان کرده‌ايم که، يک سرزمين با n نقطه در فضاي سه بعدي و حداکثر خطاي ϵ>0 را دريافت مي‌کند و در خروجي يک سرزمين ساده‌شده با سايز O(k log⁡k ) در زمان O(n^7 ) حاصل مي‌شود، که k سايز بهينه‌ي سرزمين ساده‌شده به ازاي تقريب - ϵ مي‌باشد.

چکیده

برای اعضای سایت : ۱٠٠,٠٠٠ ریال
برای دانشجویان عضو انجمن : ۲٠,٠٠٠ ریال
برای اعضای عادی انجمن : ۴٠,٠٠٠ ریال

قیمت