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

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

کلیدواژه ها:

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