فهیمه دباغی - مربی،استاد مدعو گروه علوم کامپیوتر،دانشگاه شهید باهنر کرمان
محمد مهدی قدسی - استاد،گروه مهندسی کامپیوتر گرایش نرم افزار،دانشگاه صنعتی شریف،تهرا

دراین مقاله یک الگوریتم تقریبی برای ساده سازی سرزمین مطرح شده است هدف مساله ساده سازی این است که تعداد ی از نقاط یک سرزمین حذف شود به نحوی که خطای سرزمین پس از ساده سازی بیشتر از میزان تعیین شده نباشد خطای ساده سازی به دو صورت تعریف می شود یکی اینکه پس از ساده سازی m نقطه با حداقل خطا درسرزمین وجود داشته باشد یا اینکه حداکثر خطا پس از ساده سازی به ازای کمترین تعداد نقاط E باشد این مساله در حوزه ی مسائل ان پی - سخت قرار دارد دراین راستا ما یک الگوریتم تقریبی برای ساده سازی سرزمین بیان کرده ایم که یک سرزمین با n نقطه در فضای سه بعدی و حداکثر خطای E<0 را دریافت می کند و درخروجی یک سرزمین ساده شده با سایز O(klog k درزمان O(n7 حاصل می شود که k سایز بهینه ی سرزمین ساده شده به ازای تقریب E- می باشد.

سرزمین ساده سازی،ذوزنقه ی کانونی،تقسیم بندی،الگوریتم تقریبی،برنامه سازی پویا