جلسه چهارم

هسته های هندسی

*هسته ی گستره ی نقاط (extent)

الگوریتم دقیق: O(n^c) که c ثابت است. {سه نقطه داشته باشیم به دست میاد پس n^3 تا برای ساختن دو خط موازی n تا برای چک کردن اینکه همه نقاط بین انها هستند پس c از 4 کمتر است.}

الگوریتم تقریبی: (با استفاده از هسته گستره نقاط)

محاسبه ی هسته O(n) {پیدا کردن دور ترین نقطه از یک نقطه و دورترین نقطه از یک خط}

محاسبه ی جواب دقیق مساله برای هسته: ( O( ((1/epsilon)^c')^c {اینجا c' احتمالا همان d یا d-1 و مثل آن است و یک بر اپسیلون هم تعداد نقاط هر بعد است پس کلا همان اندازه ی هسته به دست می آید.}

زمان کل: O(n+(1/epsilon)^c'c)

* تعمیم به ابعاد بالاتر (هسته ی گستره نقاط)

فرض کنید مبدا جزو نقاط باشد.

1) به ازای ابعاد از 1 تا d بعد:

2) دورترین نقطه را به ابرصفحه ی (j-1) بعدی ( j-1)-flat) ) گذرنده از مبدا و نقاط قبلی پیدا کنید.

3) عرض مجموعه نقاط به دست آمده در مرحله 2 الگوریتم را به دست آورید.

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

d*O(nd) = O(nd^2) ==> O(n)

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

تصویر بردار متناظر نقاط قبل روی ابرصفحه های (j-1) بعدی تشکیل یک پایه (نه لزوما متعامد) می دهد. می دانیم هر کدام از نقاط را می توان به صورت ترکیب خطی از بردارهای این پایه نوشت که ضرایب آنها قدر مطلقشان از 1 کمتر مساوی است (چون دورترین نقطه را هر بار انتخاب کرده ایم.)

قضیه: اگر بردار پایه بعد j-ام u_j باشد و مجموعه نقاط مرحله 2 (شامل مبدا مختصات) را S بنامیم و a هر بردار جهت دلخواه باشد، داریم:

|a.u_j| <= 2^(j-1) * width_a (S)

اثبات: استقرا روی تعداد ابعاد

پایه استقرا: یک بعد

a.u_1=a.v_1 <= width_a (S)

فرض استقرا: برای بعدهای 1 تا j-1 درست است.

حکم استقرا: برای بعد j ام:

u_j = v_j+sum_k_1_(j-1) (b_k*u_k) , |b_k| <= 1

(یعنی اگر از بردار v_j تصویر آن را در راستای بردارهای ابعاد قبل کم کنیم، تصویر آن روی ابرصفحه ی بردارهای قبلی به دست می آید.)

|a.u_j| <= |a.v_j|+sum_k_1_(j-1) (|a.u_k|)

(بردار a را در تساوی قبلی ضرب کرده ایم و از b_k <=1 استفاده کرده ایم.)

<= width_a (S)+sum_k_1_(j-1) (2^(k-1)*width_a(S) ) = 2^(j-1)*width_a(S)

(چون بردار a یکه است، ضرب داخلی آن در هر برداری تصویر آن بردار را در جهت a می دهد. که عرض نقاط از تصویر بردار در آن راستا بیشتر است.

از جلسه قبل داشتیم که دو برابر عرض نقاط از تصویر هر برداری در هر راستایی بیشتر است و تصویر بردار از عرض نقاط بیشتر است؛ که این دلیل نامساوی دومی است.)

نتیجه: به ازای هر نقطه p از مجموعه نقاط ورودی داریم:

|a.p| <= sum_j_1_d (|a.u_j|) <= sum_i_1_d ( 2^(j-1)*width_a(S) ) <= 2^d*width_a(S)

از اینجا ضریب تقریب الگوریتم را به دست می آوریم: (p و q دو نقطه از نقاط ورودی هستند)

|a.(p-q)| = |a.p-a.q| <= |a.p|+|a.q| <= 2* 2^(d) * width_a(S) =2^(d+1) * width_a(S)

==> width_a(S) <= width_a(P) <= 2^(d+1) * width_a(S)

factor = 2^(d+1)

*بهبود: 

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

(تبدیل آفین: هر تبدیلی که نقطه و خط و صفحه را حفظ کند. همه ی تبدیل های هندسی متداول آفین اند. خطوط موازی بعد از تبدیل آفین باز هم موازی خواهند بود.)

اثبات:

نقاط را در جهت بردارهای پایه (u_i) تجانس ( کلی فکر کردم یادم اومد چند برابر کردن اسمش چیه! :)) ) بدهیم طوری که اندازه ی آنها 1 بشه. (به ترتیب از بعد 1 تا d)

بعد از تبدیل:

c/2^(d+1) <= width_a(P) <= 2*sqrt(d)

چون همه ی نقاط بعدهایی بین 1 و -1 دارند، یعنی در ابرمکعب dبعدی قرار می گیرند، حداکثر فاصله شان 2 رادیکال d است. (نامساوی سمت راست)

نامساوی سمت چپ ؟؟

* هسته مجموعه نقاط P

1) تبدیل را روی P انجام بده.

2) یک توری به طول اپسیلون روی آن بساز.

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

تحلیل:

به ازای هر بردار جهت a داریم:

|width_a(S) - width_a(P)| = O(epsilon) = O(epsilon*width_a(P))

تساوی آخر به دلیل داشتن مقدار حداکثر عرض نقاط است. (به دلیل تبدیلی که انجام دادیم و نامساوی قبل)

width_a(S) / width_a(P) = 1-O(epsilon)

==> O(epsilon)-coreset

اندازه هسته:

#grid cells = O(1/epsilon^d)

*مساله عرض نقاط:

O(n+(1/epsilon^d)^ceil(d/2) ) {using exact algorithm}

O(n+1/epsilon^((d-1)/2)*1/epsilon^((d-1)/2) ) = O(n+1/epsilon^(3/2(d-1)) ) {using algorithm 1: dir. rounding+skewed width}

d-1 برای این است که می توان با پیدا کردن دورترین نقطه در یک بعد مساله را حل کرد.

نکته: بعد از تبدیل گرفتن جهت ها را رند کنیم.

نکته: می توانیم از نوعی دیاگرام ورونوی گسسته استفاده کنیم. {نزدیک ترین نقطه به جای دورترین نقطه که در قطر استفاده کردیم.} که این کار زمان زیر را می دهد:

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

نکته: بهترین اندازه هسته ممکن:

O(1/epsilon^((d-1)/2) ) {by Agrawal}

نکته: هسته گستره نقاط برای پوسته محدب کار می کند.

نکته: هسته گستره نقاط برای مسائل دیگری مثل پیدا کردن دو دایره هم مرکز با کمترین فاصله که همه ی نقاط را بپوشانند؛ هم کار می کند.