بخشی از مقاله
چکیده
در این مقاله الگوریتمی جدید برای تولید چندضلعیهای ساده تصادفی برگرفته شده از معکوس درخت کاستی تحدب، ارائه میدهیم. درخت کاستی تحدب یک ساختار درختی است که چندضلعی ساده را در لایه های محدب نمایش میدهد. این الگوریتم قادر به تولید یک چندضلعی است که درخت کاستی تحدب آن برابر با درخت کاستی تحدب داده شده در ورودی است. به بیانی دیگر از روی یک درخت تصادفی با توزیع یکنواخت، یک چندضلعی ساده تولید میشود. این چندضلعی نماینده تمامی چندضلعیهایی است که درخت کاستی تحدب آنها با درخت ایجاد شده یکسان است. این روش اولین بار است که در تولید چندضلعیهای تصادفی ارائه میشود. این الگوریتم دارای پیچیدگی زمانی O - K 2 - است. که در آن K تعداد گرههای درخت و تعداد اضلاع چندضلعی میباشد.
-1 مقدمه
هندسه محاسباتی از شاخههای علوم کامپیوتر است که برای حل مسائل هندسی مورد استفاده قرار میگیرد. از مسائلی که در زمینه هندسه محاسباتی مطرح است مسئله تولید چندضلعی ساده تصادفی است. که از آن میتوان در زمینه بررسی صحت الگوریتمها و ایجاد اشکال برداری تصادفی استفاده کرد. از این رو مسئله تولید چندضلعی تصادفی از دیر باز مورد توجه محققان قرار گرفته است و روشهای اکتشافی زیادی برای تولید چندضلعیها تصادفی ارائه شده است. که این روشها منجر به تولید کلاسهای ویژهای از چندضلعیها به نام چندضلعی گل خورشیدی، چندضلعی ستارهای شکل و چندضلعی یکنوا شده است. که هرکدام از این دسته از کلاسهای چندضلعی در مرتبه زمانی مختلفی قادر به تولید چندضلعی ساده میباشند، اما هیچکدام قادر به تولید تمامی حالات چندضلعی ساده با توزیع یکنواخت نمیباشند.
.[3-1] شاخه دیگری از علوم کامپیوتر که توجه محققین را به خود جلب کرده است، تولید درخت تصادفی میباشد که نتیجه تحقیقات محققان تولید تصادفی درختان مختلفی همچون، تولید تصادفی درخت دودویی، تولید تصادفی درخت پوشا1، تولید تصادفی درخت مرتب2 و تولید تصادفی درخت ریشهدار3 می-باشد.[8-4] در این مقاله یک روشکاملاً جدید برای تولید چندضلعی ساده به نام 4RCDT ارائه خواهد شد. این روش از روی درخت ریشهدار، با پیمایش پس ترتیب5 چندضلعی ساده تصادفی را تولید میکند. در بخش 2 این مقاله به شرح الگوریتمRCDT پرداخته شده و در بخش 3 نحوه تولید چندضلعی ساده از روی گرههای غیر برگ درخت را شرح میدهد. در بخش 4 نحوه رفع تداخل اضلاع چندضلعی را بیان میکند، و در بخشهای 5 و 6 تحلیل الگوریتم به همراه نتیجه گیری بیان شده است.
-2 الگوریتم RCDT
میتوان چندضلعیهای ساده را با یک ساختار درخت کاستی محدب6 نمایش داد .[6] روش کار به این صورت است که چندضلعی P را در قالب چندضلعی محدب CH - P - در نظر گرفته و تفاضل بینP و CH - P - مجموعهای مجزا از چندضلعیها را به ما میدهد. که هر کدام از این چندضلعیهای مجزا را به عنوان فرزندان چندضلعی P در نظر میگیریم؛ و برای هر کدام از فرزندان نیز به همین ترتیب عمل کرده و آنها را در قالب محدبشان قرار داده و درخت را گسترش میدهیم تا جایی که به چندضلعی برسیم که محدب باشد و فرزندی نداشته باشد. به بیان دیگر تمامی برگهای CDT چندضلعی محدب میباشند. شکل CDT 1 چندضلعی P را که به رنگ خاکستری است نمایش میدهد. الگوریتم ارائه شده در این مقاله از عکس روشCDT بهره میبرد و از آن برای تولید چندضلعیهای ساده تصادفی استفاده میکند. بنابراین میتوان روند کلی الگوریتم RCDT را به شرح زیر بیان کرد.
· ایجاد یک درخت تصادفی یکنواخت برای تولید یک n ضلعی ساده تصادفی.
· تولید چندضلعی ساده تصادفی از روی درخت ایجاد شده در مرحله قبل.
-1-2 تولید درخت تصادفی یکنواخت
در این بخش برای تولید CDT تصادفی از روش تولید درخت ریشهدار تصادفی با توزیع یکنواخت، استفاده میکنیم.[8] پس از تولید درخت تعداد اضلاعی که از گرههای درخت در چندضلعی تولید شده مورد استفاده قرار میگیرد را محاسبه میکنیم. که در آن تعداد اضلاع چندضلعی است، که از گره ام درخت تولید میشود. مقدار اگر گره برگ باشد برابر با 2 و اگر گره غیر برگ باشد و یک یا دو فرزند داشته باشد، برابر با یک و اگر گره غیر برگ با فرزند - > 2 - باشد، برابر با − 1 میباشد.
ممکن است که در حین تولید چند ضلعی بتوان بعضی از اضلاع را با طول یک - نقطه - در نظر گرفت، یا اینکه بعضی از اضﻻع در امتداد ضلع قبلی خود با همان زاویه و شیب باشند، به عبارتی دیگر میتوان از مقدار در هنگام اجرای برنامه کاست، که این امر باعث کاهش مقدار میگردد. در رابطه - 1 - عدد یک به این دلیل اضافه شده است که در هر مرحله، چندضلعی که از گره تولید میشود از طرف یک ضلعش به پدر خود متصل میشود و در حقیقت آن ضلع حذف میشود، اما چندضلعی گره ریشه چنین شرایطی را ندارد. برای آنکه چندضلعی به صورت تصادفی با تعداد اضلاع مختلف تولید شود، یک عدد بزرگتریا مساوی که بیانگر تعداد اضلاع چندضلعی میباشد را به تصادف انتخاب میکنیم. و به مقدار اختلاف − مقدار گرههای مختلف درخت را افزایش میدهیم.
-2-2 تولید چندضلعی ساده تصادفی از روی درخت تصادفی
در روشRCDT هر گره از درخت نماینده یک چندضلعی است. که با پیمایش پسترتیب درخت و ملاقات گرهها، این چندضلعیها به هم متصل شده و گستردهتر میشود. و در نهایت با ملاقات ریشه چندضلعی تکمیل میگردد. روش ساخت چندضلعی برگهای درخت با گرههای غیر برگ متفاوت است. که در ادامه روش ساخت هرکدام را جدا گانه شرح میدهیم.
الف : تولید چندضلعی از روی گرههای برگ - تولید چندضلعی محدب دلخواه - درCDT هرکدام از برگهای درخت نماینده یک چندضلعی محدب میباشد. بنابراین در روش RCDT هر برگ یکچند ضلعی محدب تصادفی است. تاکنون روشهای مختلفی برای تولید چندضلعی محدب تصادفی توسط محققین ارائه شده است.[10 ,9] تولید یک چندضلعی محدب تصادفی در مرتبه زمانی - - خواهد بود و تعداد اضلاع چندضلعی محدب برابراست با = + 1 که در آن تعداد اضلاع چندضلعی است، که از گره ام درخت تولید میشود - یک ضلعی اضافه برای اتصال چندضلعی گره برگ به چندضلعی پدر خود میباشد - .
ب: تولید چندضلعی گرههای غیر برگ برای تولید چندضلعی گرههای غیر برگ میبایست چندضلعی محدبی تولید کرد که این چندضلعی محدب بتواند بدون هیچگونه تداخلی، چندضلعی فرزندانش را در درون خود جای دهد. در هنگام جای دهی فرزندان درون چندضلعی پدر، به منظور کم کردن پیچیدگی زمانی مربوط به بررسی وجود تداخل فرزندان، فرزندان را در قالب پوسته محدبشان در نظر میگیریم[11] و از پوسته محدب فرزندان برای بررسی وجود تداخل استفاده میکنیم. در پایان فرزندان را از قالب محدبشان خارج میکنیم. شکل 2 بهطور نمونه یک چندضلعی فرزند را در قالب پوسته محدبش نمایش میدهد.
از بین این n ضلع، + 1 ضلع آن در چندضلعی حاصل از این گره وجود خواهند داشت و مابقی اضلاع تنها برای نشان دادن محل قرارگیری فرزند به چندضلعی غیر برگ استفاده میشوند و در چندضلعی نهایی نمایش داده نمیشوند. در شکل 2 اضلاع 0و2و 4و6 از چندضلعی محدب، اضلاع واقعی هستند، و اضلاع 1و3و5 محل اتصال فرزند میباشند. ضلع صفر، در صورتی که گره مربوط به این چندضلعی ریشه نباشد، به عنوان محل اتصال به پدر در نظر گرفته میشود.
برای تولید چندضلعی محدب غیر برگ، چندضلعی محدب را به چهار ناحیه تقسیم میکنیم و هر ناحیه را به طور مجزا همراه با الحاق فرزندانش تولید کرده و در آخر ناحیهها را به هم متصل میکنیم. که روش انجام این مراحل را در ادامه به طور مجزا در بخشهای سه و چهار شرح میدهیم. -3 ناحیه بندی چندضلعی محدب غیر برگ و تولید چندضلعی محدب دلخواه تمامی چندضلعیهای محدب را به چهار ناحیه زیر میتوان تقسیم کرد که عبارتاند از:
· ناحیه اول ناحیهای است که اضلاع در جهت افزایش مختصات و حرکت میکنند.
· ناحیه دوم ناحیهای است که اضلاع در جهت کاهش مختصات و افزایش مختصات y حرکت میکنند.
· ناحیه سوم ناحیهای است که اضلاع در جهت کاهش مختصات و حرکت میکنند.
· ناحیه چهارم ناحیهای است که اضلاع در جهت افزایش مختصات و کاهش مختصات حرکت میکنند.
بعضی از چندضلعیهای محدب مانند مثلث تنها شامل سه ناحیه میباشند. که در آن یکی از دو ناحیههای یک یا چهار تعداد اضلاعش صفر است. و مابقی ناحیهها حداقل تعداد اضلاعشان یک است. برای تولید چندضلعی غیر برگ، اضلاعی را که محل الحاق فرزندان به چندضلعی پدر میباشند را به صورت غیر متوالی و تصادفی انتخاب میکنیم، همچنین تعداد اضلاع هر ناحیه را به تصادف مشخص میکنیم، به گونهای که مجموع اضلاع ناحیهها برابر با − 1 باشد - یک ضلع برای اتصال ناحیهها و اتصال چندضلعی به پدر، مورد استفاده قرار میگیرد - .
-1-3 تولید ناحیههای چندضلعی محدب غیر برگ
در این بخش ناحیه اول و دوم از چندضلعی محدب غیر برگ را تولید میکنیم. و برای تولید ناحیه سه و چهار همانند ناحیه یک و دو عمل میکنیم. برای تولید ناحیه یک از ضلع پایین - کمترین مختصات - شروع و به سمت بالا حرکت میکنیم. و برای تولید ناحیه دو از ضلع بالا - بیشترین مختصات - شروع و به سمت پایین حرکت میکنیم . بنابراین در ناحیه دوم اضلاع در جهت افزایش مختصات و کاهش مختصات حرکت میکنند.
برای تولید اولین ضلع از ناحیه یک و دو، در ابتدا یک خط فرضی موازی محور ها تولید میکنیم و از آن ضلع شروع به تولید اضلاع ناحیهها میکنیم. در صورتی که اولین ضلع از ناحیه دو، فرزندی برای الحاق شدن به آن در نظر گرفته نشده باشد، برای تولید ضلع دوم از ناحیه دو نیز ابتدا یک خط فرضی موازی محور ها تولید میکنیم و از آن ضلع شروع به تولید اضلاع ناحیه میکنیم . به طوری که اضلاع ناحیهها با این خطوط فرضی برخورد نداشته باشند.
