ترجمه مقاله تجزیه چند ضلعی محدب ساده درزمان محدود

توضیحات

عنوان فارسی: تجزیه چند ضلعی محدب ساده درزمان محدود

عنوان انگلیسی:

On the time bound for convex decomposition of simple polygons

چکیده:

ما نشان می دهیم برای تجزیه پلیگون های ساده nراسی دارای  rمقدار واکنش غیرارادی ,درحد اقل ناحیه محدب بدون اضافه کردن رئوس قابل محاسبه در  زمان و فضاست.نسخه نمایشی جاوا در دسترس است:

مقدمه:

فرض کنید که Pیک پلیگون ساده باnراس است که ,rمقدار از انها انعکاسی(refiex)وزوایای داخلی آنها بزرگتر از  است.حداقل مشکل تجزیه محدب درخواست یک تجزیه داخلی پلیگون p به منظور]یافتن[  کمترین مقدار ناحیه محدب است .یک نا هنجاری در ادبیات حداقل تجزیه محدب وجود دارد:که بند استفاده شده درتجزیه می تواند نقاط اشتاینر را به صورت دلخواه پایان دهد,مثل شکل یک ,سپس Chazelle & Dobkin[2,3]نشان دادند که تجزیه حداقل می تواند به وسیله برنامه نویسی دینامیک در زمان محاسبه شود.به عبارت دیگر , اگر بند باید در رئوس پلیگون پایان پذیرد ,مثل شکل2,پس بهترین مرز مطرح شده الگوریتم دینامیک برنامه ی keilاست[9,10]که حداقل تجزیه در  زمان محاسبه میشود.همانطور که Chazelle&Dobinkدر 1985مطرح کردند.این به صورت موازی برای هرمقدار غیر ثابتr آرامتر است,با اینکه معمولااجازه می دهد  نقاط اشتاینر بهینه سازی مشکلات را سخت کند.

بعد از چند تعریف , ما در قسمت سه نشان خواهیم داد که الگوریتم برنامه نویسی دینامیک Kelin می تواند در فضای ساختار تحقیق مئورد استفاده اجرایی قرار گیرد ,که فاکتوراز زمان اجرا حذف می کند.در قسمت 4 نشان خواهیم داد که ورودی در زمان کاهش یابد برای  پلی گونی که دارای حد اقل تجزیه یکسان ولی فقط اندازه است.بنابراین , یک تجزیه حداقل ازPمی تواند در  زمان محاسبه کرده  وزمان حداقل اجرا زمانیChazell&Dobkin که تطابق دهد .  اگرزمان استفاده از کاهش ساده داده شود ما پلی گونی را که فقط اندازه  دارد را بدست می اوریم . این ممکن است سختی ظاهر پلیگون های نقاط اشتانر را توضیح دهد .یک مشکل وابسته پیدا کردن تجزیه محدب با کمترین مقدار جوهرکه دارا ی حداقل اندازه لبه  است . ما می توانیم ساختار تحقیق از الگوریتم حداقل جوهر Keil به بدست آوردن  زمان ساده کنیم اما نمی توانیم وابستگی به nرا کاهش دهیم.

نماد سازی برای چند ضلعی ساده

فرض کنید که ما nراس از یک پلیگون  را به صورت پاد ساعت گرد گرفته ایم . ما فرض می کنیم که Pساده است : که فقط تقاقع بین لبه ها ی پلی گون قسمت که از مرز Pناحیه ای که انتهای مجاور لبه ها اشتراک دارد .

قطر Pقسمتی است که دو راس P به هم می پیونددو به سختی در pباقی میماند ما ازعلامت  برای قطر با استفاده کرده ایم . بر اساس قرار داد ما خواهیم گفت که  نیز یک یک قطر است , گاهی اقات ما اجازه خواهیم داد که   یک لبه پلیگون را زمانی که  تعریف کند . قطر ها برا ی گرفتن راس  می توانند به وسیله محاسبات برای  یافت ,که با زمان خطی linear timمحقق می شود . مشاهداتی که در ادامه ذکر شده است برای پایداری الگوریتم مهم است و برا ی ما نیز مهم خواد بود .

مشاهده 1

راستای قطر ها به صورت پاد ساعت گرد برای راس  است همانند راستای نقطه انتهایی اطراف P.

راس Pمعکوس خواد شد اگر زاویه داخلی بزرگ تر از  باشد . دیدن حداقل تجزیه محدب بدون نقطه ی اشتاینر سخت نیست باد از قطری که حد اقل راس انعکاسی را دارد استفاده کرد . در حقیقت یک راه ساده برا ی به دست اوردن تجزیه در حداکثر 4 مرتبه بیشترین تعداد قطعه ی محدب است که با مثلث بندی P که شامل هر قطر به نوبه خود است وقطر هایی را که کمترین شکل زاویه انعکاسی در نقطه ی انتهایشان دارند  حذف می کند .

برنامه نویسی دینامیک برا ی تجزیه محدب

برای حل مشکل حداقل تجزیه محدب ما از برنامه نویسی پویا استفاده می کنیم , که الگویی الگوریتمیک  با بهترین راه حل را برای مشکل به وسیله ترکیب کردن راه حل هایی بهینه برای مشکلات زیر  دارد[1]:

1. تعریف زیر مسئله

ما یک زیر مسئله برای هر قطر  تعریف می کنیم, که از حداقل راس انعکاسی استفاده می کند ;اجازه می دهد  خطی از پلیگون  معنی دهد.نه این که به وسیله اضافه کردن قطر  به  یک پلیگون داخلی به دست آوریم. اندازه زیر مسئله به تعداد راس ها در  است ; که زیر مسئله را از کوچک ترین به بزرگترین حل میکند وبه ما حداقل تجزیه  که حداقل تجزیه Pنیز است را میدهد.

ما  را با وزن  وابسته کرده ایم که حداقل تعداد قطر های لازمه برای بدست آوردن تجزیه محدب  است.

با قرارداد است . ازانجایی که ممکن است به صورن خیلی تصاعدی رسیدن به وزن  باشد .Keil[9]پیشنهاد داد  که فقط کلاس های هم ارزی مشخصی ذخیره سازی شوند . هر کلاس می تواند نمایش داده شود به وسیله ی یک جفت تابع قطر و لبه تا  و  که کران ناحیه محدب هستند به  محدود شوند.چرا که این جفت ها رابط بین زیر مسئله ها ی روی دوقسمت فرم می دهند.به صورت اختصاصی ما ذخیره می کنیم باریک تیرن جفتی که ناحیه محدب در یک همسایگی از  شامل ناحیه محدب از حداقل تجزیه  نمی شود .

طبق مشاهدات 1 ما می توانیم برای باریکترین جفت  ها به وسیله شاخص تست آزمایش کرد .

شکل سه مثالی برای با 12 تجزیه محدبش را نشان میدهد که فقط سه قطر  را استفاده می کند :در سطر ها ما یکی از انتخاب می کنیم ودر ستون ها ما  را با  یا  را با  یا  انتخاب می کنیم.

نازکترین تجزیه ها ,دور گرفته شده اند ,در سه کلاس هم ارزی افتاده اند . همان طور ما شاخص هایی برای جفت های باریک در دسته   ذخیره سازی کرده ایم بنابراین بند از پایین به بالا به صورت پاد ساعت گرد دور وهستند.

دسته  برای شکل سه شاملو  از پایین تا بالا  می شود . به دین ترتیب , ما می دانیم که قطر  و لبه به باریک ترین جفت که دورترین پادساعت گرد تشکیل شده.

2. حل زیر مسئله

این مهم است که مشاهده شود که هر حداقل تجزیه محدب می تواند به وسیله بررسی های اولیه زیر مسئله ها ی تعریف شده که با قطر هایی که حداقل یک نقطه ی انتها راس انعکاسی دارند ,می توان یافت .  یک راه برای ساختن این امر تعریف مثلث بندی استاندارد برای حداقل تجزیه محدب است .

ما فرض کردیم که راس هم به طور قراردادی یا به طور باز شماره گذاری رئوس Pاز پیش محدب نبوده . سپس هر تجزیه محدب می تواند برای مثلث بندی استاند دارد کامل شود : در هر ناحیه محدب رئوس انعکاسی با اندکس چایین به رئوس انکاسی با اندکس بالا وصل می شوند .اگر راسی وص نشده باقی بماند در ناحیه ,راس با بیشترین اندکس در ناحیه این راس را به رئوس دیگر متصل می کند . در شکل چهاررئوس بین   و  و رئوس بین  متصل شده اند به بیشترین اندکس ; در دیگر نواحی به کمترین مقدار اندکس وصل شده اند .

توجه:

• برای دانلود فایل word کامل ترجمه لطفا اقدام به خرید فرمایید.
• پس از خرید بلافاصله لینک دانلود فایل برای شما ایمیل خواهد شد.

سفارش ترجمه مقاله

به منظور سفارش ترجمه تخصصی مقالات خود بر روی کلید زیر کلیک نمایید.

سفارش ترجمه تخصصی