مثلث بندی

(واقعا ناراحت کننده است که هیچ کدام از توانایی های من برای هیچ کس ارزش نداره.)

یک چند ضلعی را با رسم کردن یک سری یال به مثلث تقسیم کنیم.

1- پیدا کردن قطر

از سمت چپ ترین راس چند ضلعی شروع می کنیم و راسهای دو طرف آن را به هم وصل می کنیم، (فکر کنم این حلش می کنه:) اگر به هم وصل کردیم و بقیه ضلع ها را قطع نکرد جواب است، وگرنه به سر پاره خطی که قطع کرده وصل می کنیم. (سوال امتحان بود که اشتباه گرفتم با قطر چندضلعی محدب!)

هر بار یک قطر پیدا می کنیم، چند ضلعی به دو قسمت تقسیم می شود، هر کدام از این قسمتها را بازگشتی حل می کنیم.

زمان الگوریتم: پیدا کردن قطر: O(n)

T(n) = T(n-1)+O(n)

T(n) = O(n^2)

1- 2- بهبود: قطری را پیدا کن که هر دو چندضلعی کمتر از 2/3n ضلع داشته باشند.

T(n) = 2T(2/3n)+O(n)

T(n) = O(nlogn)

2- استفاده از تجزیه ذوزنقه بندی

اول ذوزنقه بندی را به دست می آوریم، اگر دو راسی که ذوزنقه را می سازند مال یک پاره خط نباشند، آنها را به هم وصل می کنیم. (شکل بکشید!)

چندضلعی های ساخته شده را مثلث بندی کنید.

چندضلعی های ساخته شده با این روش همه half monotone هستند، یعنی هر خط عمودی آنها را در دو نقطه قطع می کند. با graham scan می توان هر چند ضلعی به این شکل را در زمان خطی مثلث بندی کرد. (graham scan: نقاط را یکی یکی اضافه می کند و ccw بودن کنج ساخته شده را چک می کند.)

زمان الگوریتم:

O(nlogn)+O(n)+O(n) = O(nlogn)

زمان ذوزنقه بندی+زمان اضافه کردن یال به ذوزنقه ها+زمان مثلث بندی چند ضلعی های half monotone

نکته: برای چند ضلعی های دارای سوراخ هم کار می کند.

نکته: می توان زمان sort را حذف کرد.

3- الگوریتم افزایشی تصادفی تغییر یافته (سیدل)

به ذوزنقه بندی یکی یکی پاره خط اضافه می کنیم، اگر این پاره خط شماره ی ceil(n/logn^h) بود که h بین 1 و log*n است، ذوزنقه ی شامل یک سر این پاره خط را پیدا می کنیم و بقیه را از روی آن پیدا می کنیم. زمان آن logk/j می شود که k تعداد ذوزنقه هایی است که قطع می کند و j شماره ی ذوزنقه ی اول است. (یعنی ساختمان داده را به روز می کنیم.)

با این کار زمان الگوریتم nlog*n می شود.