جلسه دوم

ادامه ی الگوریتم های محاسبه قطر نقاط

3- الگوریتم تقریبی agrawal, matousek, suri 1992

ایده: رند کردن جهت ها (به جای اینکه نقاط ورودی را رند کنیم، نقاط خروجی را رند می کنیم.)

1- مجموعه ای از جهت ها به دست بیاور. (هر جهت a)

2- نقاط مرزی p_a و q_a را در جهت a به دست بیاور.

3- ماکسیمم فاصله نقاط مرزی را به ازای همه ی جهت ها برگردان:

diameter = max_a ( ||p_a - q_a|| )

سوال: اگر جهت هایی که در نظر می گیریم بردارهایی باشند که با هم زاویه مساوی می سازند (یکنواخت باشند)، به چندتا از آنها نیاز داریم تا فاصله ی هر بردار دلخواه تا آنها فاصله ی حداکثر delta داشته باشد؟ (در فضای d-بعدی)

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

3D:

a=(teta_i, teta_j,teta_k)

v=(a_i,a_j,a_k)

a-v =(teta_i-a_i, teta_j-a_j, teta_k-a_k)

||a-v|| = sqrt( (teta_i-a_i)^2+(teta_j-a_j)^2+(teta_k-a_k)^2) = delta

d-dimensions:

delta_teta = sqrt(1/d)*delta

که delta_teta زاویه بین دو بردار متوالی در هر بعد است. پس تعداد کل بردارهای لازم:

#vectors in 2-d = 2*pi/delta_teta = 2*pi*sqrt(d)/delta

#vectors in d-dimensional space = (#angles in each plane from each base vector)^(d-1)

= (2*pi*sqrt(d)/delta)^(d-1)

= O( 1/delta^(d-1) )

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

*محاسبه ضریب تقریب الگوریتم

فرض کنید قطر بهینه بین نقاط p و q باشد.

تصویر بردار p به q را روی بردار a می خواهیم به دست بیاوریم. (برای این کار می توانیم ضرب داخلی دو بردار را حساب کنیم چون بردار a یکه است.)

|q_a-p_a| >= (q-p).a = |q-p|.|a|.cos (teta) = |q-p|.cos(teta)

(0<= teta <= delta ==> cos(delta) <= cos(teta) <= 1 )

projection >= |q-p|.cos(teta) >= |q-p|.cos(delta)

ALG >= OPT.cos(delta)

( cos(delta) > 1-(delta^2)/2 )

OPT >= ALG >= OPT.(1-(delta^2)/2)

factor: 1-epsilon

(epsilon = (delta^2)/2)

*زمان اجرا

=هزینه ی تصویر کردن نقاط در این بعدها

#points * #directions = n*1/O(epsilon^((d-1)/2)) = O( n/epsilon^*(d-1)/2) )

4-بهبود الگوریتم قبل

ایده: ترکیب الگوریتم های 2 و 3 برای به دست آوردن تقریب بهتر

الگوریتم:

1) رند کردن نقاط به نقاط توری (الگوریتم 2)

2) رند کردن نقاط جدید در جهت های مختلف (الگوریتم 3)

*ضریب تقریب الگوریتم

ضریب تقریب آنها در هم ضرب می شود:

(1-epsilon)(1-epsilon)=1-2epsilon=1-epsilon'

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

step1: O( n+1/epsilon^(d-1) ), n'=#grid_pts = 1/epsilon^(d-1)

step2: O(n'*1/epsilon^(d-1)/2)

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

5-الگوریتم چان

ایده:

-قدم آخر الگوریتم 2 را به صورت بازگشتی روی d حل کنیم.

-زیرمساله کلی تری را حل کنیم: دیاگرام ورونوی گسسته (DVD)

**دیاگرام ورونوی گسسته

تعریف مساله: مجموعه ای P از n نقطه از رئوس توری d بعدی u x u داده شده است، به ازای هر نقطه q کوئری (dبعدی) دورترین همسایه از q را از بین نقاط P پیدا کنید.

راه حل معمولی: امتحان کردن همه ی حالت ها:

O(n^2)

#points = n <= #grid points = u^d

O( u^(2d) )

مشاهده: دورترین همسایه نسبت به نقطه = دورترین همسایه نسبت به راس توری متناظر آن نقطه

اثبات:

نقطه q، دورترین همسایه p، راس توری متناظر نقطه q^

اثبات با شکل: فرض کنید وسط لابی دانشکده ایستاده اید، سر شما نقطه q است و دورترین نقطه در صفحه ی کف دانشکده (که توری هم هست!) نقطه ی p است و پای شما نقطه ی q است. هر نقطه ای که در صفحه ی کف دانشکده نسبت به سر شما دورترین باشد، نسبت به پای شما هم دورترین است.

(فرض کنید روی یکی از راسهای توری ایستاده اید چون کلا مساله گسسته است)

الگوریتم دیاگرام ورونوی گسسته: (d بعد، مجموعه نقاط P)

1) دیاگرام ورونوی گسسته را برای صفحه های توری عمود بر محور d به دست بیاورید. (همین تابع را با d-1 صدا کنید.)

2) برای هر خط عمودی توری L، دورترین همسایه هایی که در مرحله ی 1 نسبت به این خط پیدا کرده اید (چون در مرحله قبل برای همه ی خطوط توری حساب کرده بودیم)، S_L بنامید.

3) برای هر نقطه توری q روی خط L، دورترین همسایه ی q از اعضای S_L را گزارش کنید.

تحلیل:

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

u^(d-1) = #grid cells in (d-1) dimensions (u x u grid)

u = #points in current dimension

u = finding the farthest point in u (d-1)-hyper-plane (grid)

==> T(d,u) = u*T(d-1,u)+O(u^(d-1)*u*u)

T(1,u) = O(u^2)

T(d,u) = O(u^(d+1))

*زمان الگوریتم قطر 4 (چان)

(در مرحله ی آخر الگوریتم 2(توری) از دیاگرام ورونوی گسسته استفاده کرد.)

u=1/epsilon d'=d-1==>d'+1=d

O(n+1/epsilon^d)

*ضریب تقریب مثل قبل.

*بهترین الگوریتم فعلی:

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

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