جلسه اول

قطر: تعدادی نقطه در فضای d-بعدی داده شده است، فاصله ی دورترین دو نقطه چقدر است؟

for all p,q in P: diameter = max_p_q (distance(p,q)) = max_p_q( ||p-q|| )

کاربردها: ساده ترین روش برای پیدا کردن شکل نقاط است.

الگوریتم دقیق:

1-به دست آوردن فاصله ی همه ی زوج نقطه ها و ماکسیمم گرفتن: O(n^2)

2-استفاده از anti podal pair (زوج خطوط موازی که همه نقاط بین آنها قرار می گیرند): O(nlogn)

- در دو بعد با به دست آوردن پوسته محدب نقاط

3- در سه بعد با روش تصادفی clarkson, shor 1998، روش قطعی Ramos 1991 زمان O(nlogn)

4- در چهار بعد O(n^4/3 polylog(n)) ارائه شده توسط Matousek 1992

5- در d بعد O(n^ (2-2/(ceil(d/2)+1))

الگوریتم تقریبی:

تعریف جدید مساله: diameter را طوری پیدا کنید که به ازای ثابت c داشته باشیم:

diameter <= diameter_OPT <= c*diameter

الگوریتم های تقریبی:

0- یک نقطه دلخواه از بین نقاط را برداریم و فاصله ی دورترین نقطه از بین نقاط از آن را به عنوان قطر برگردانیم.

زمان: O(dn) : این بهترین زمانی است که برای حل این مساله هست.

ضریب تقریب: 2

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

مزیت الگوریتم: یک بار دیدن داده ها برای آن کافی است. این در الگوریتم هایی که روی جویبار داده (data stream) کار می کنند مهم است.

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

زمان الگوریتم: O(dn)

برخلاف الگوریتم قبلی دو بار باید داده ها را ببیند.

ضریب تقریب: رادیکال 3

اثبات ضریب تقریب:

نقطه دلخواه را p بگیرید دورترین همسایه آن را q بگیرید و t را دورترین نقطه از دورترین همسایه بگیرید.

می خواهیم بین فاصله ی q و t (جواب الگوریتم) و بیشترین فاصله زوج نقاط (جواب بهینه) یک رابطه به دست بیاوریم.

دایره به مرکز q و شعاع قطر نقاط (به دست آمده از الگوریتم که همان ||q-t|| است) می زنیم. همه ی نقاط درون این دایره می افتند چون t دورترین نقطه به q است. نقطه ی p هم درون این دایره است. از مرکز دایره q به p یک خط رسم کنید تا محیط دایره را قطع کند و از آنجا یک دایره به شعاع قطر به دست آمده از الگوریتم بزنید. این دایره از q می گذرد، چون مرکز آن روی محیط دایره بوده و شعاع آن با شعاع این دایره برابر بوده است. مرکز این دایره دوم را o بنامید.

به ازای هر نقطه از نقاط ورودی مثل x می دانیم فاصله ی آن از o کمتر از جمع فاصله x از p و فاصله p از o است (نامساوی مثلث):

||x-o|| <= ||x-p||+||p-o|| <= ||p-q||+||p-o||=||o-q|| = r = ||q-t||

یعنی همه ی نقاط درون این دایره دوم هم می افتند.

دورترین فاصله ی دو نقطه در اشتراک این دو دایره، فاصله ی نقاط تقاطع آنها است، که رادیکال سه برابر شعاع دایره ها می شود. پس ضریب تقریب رادیکال 3 است.

{اگر به مرکز p و شعاع ||p-q|| دایره می زدیم، همه ی نقاط درون آن بودند چون دورترین نقطه از p نقطه q بود. به جای آن از دایره ای که این دایره به آن مماس داخل بود استفاده کردیم که هم شامل این دایره بشود هم تحلیل ساده تر باشد. در واقع بدترین حالت را در نظر گرفتیم که p دورترین نقطه به q بود علاوه بر t!}

2- الگوریتم Barequet, Har-Peled 1999

ایده: رند کردن نقاط با استفاده از توری {به نزدیک ترین گوشه توری}

{این الگوریتم از الگوریتم های تقریبی است که درون آنها از یک الگوریتم تقریبی دیگر استفاده می شود. همان حالتی که ضریب تقریب ها در هم ضرب می شوند.}

1) یک جواب تقریبی با یکی از الگوریتم های قبلی به دست بیاور. (ضریب تقریب آن را c فرض کنید.)

2) به ازای یک epsilon توری diameter*...*diameter با خانه های به طول epsilon*diameter بساز. (تعداد خانه های توری به این صورت است:)

c*diameter/(epsilon*diameter) *...* c*diameter/(epsilon*diameter) = (c/epsilon)^d

3) هر نقطه از نقاط داده شده را به نزدیک ترین گوشه ی خانه های توری رند کن.

4) فاصله ی دورترین نقاط جدید (راسهای توری) را به عنوان قطر برگردان.

زمان اجرا :

تعداد نقاط جدید (رند شده) = حداکثر به تعداد نقاط توری =

(2^d)*(c/epsilon)^d

{دو به توان d تعداد گوشه های هر خانه توری در d بعد است! برای دو بعد می شود 4 گوشه!}

مشاهده می کنیم که تعداد این نقاط به تعداد نقاط ورودی مربوط نیست، در نتیجه ثابت است و زمان الگوریتم شامل ساخت توری و محاسبه جواب به صورت زیر است:

O( n+1/(epsilon^2d) )

که قسمت O(n) مربوط به ساخت توری و قسمت O((1/epsilon)^2) مربوط به اجرای الگوریتم دقیق O(n^2) روی نقاط توری است.

ضریب تقریب: 1+epsilon

اثبات:

فاصله ی هر نقطه تا نقطه ی رند شده ی آن یعنی نزدیک ترین گوشه ی خانه ی توری که یک مکعب d بعدی به طول ضلع epsilon*diameter است، حداکثر به اندازه ی نصف قطر مکعب است (حالتی که نقطه دقیقا وسط مکعب باشد) یعنی:

(epsilon*diameter)*1/2*sqrt(1+1+...+1) = (epsilon*diameter)*sqrt(d)/2

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

||p-q|| <= ||p-p'||+||p'-q||

||p'-q|| <= ||q-q'||+||p'-q'||

==> ||p-q||-||p'-q'|| <= ||p-p'||+||q-q'|| <= (epsilon*diameter)*sqrt(d)/2*2 = (epsilon*diameter)*sqrt(d)

==> |diameter-diameter_OPT| <= diameter*(epsilon*sqrt(d))

==> diameter_OPT*(1-epsilon*sqrt(d)) <= diameter <= diameter_OPT*(1+epsilon*sqrt(d))

یعنی یک 1+epsilon تقریب برای قطر است.

3-بهبود الگوریتم:

برای هر سطر (یک بعد از توری) نقاط مینیمم و ماکسیمم را نگه داریم.

ضریب تقریب:

O( n+1/(epsilon^2(d-1)) )

روش و اثبات:

{فکر کنم منظورش این باشه که توی هر ابرصفحه ی توری مینیمم و ماکسیمم را در یک بعد نگه داریم، چون اگر توی کل مجموعه باشه که درست جواب نمیده. مخصوصا از تعمیمی که داده این طور به نظر میاد.}