تقریب قطر با استفاده از جعبه محیطی با کمترین حجم در سه بعد

http://graphics.stanford.edu/courses/cs468-06-winter/Slides/an_bounding_box_fall.pdf

تعریف ریاضی توری و یک خانه از آن

محاسبه ی قطر با استفاده از توری

الگوریتم جستجو روی توری با استفاده از جهت ها

جلسه ششم

الگوریتم 2: برای عرض در 2 بعد با تقریب ثابت (chan 2004)

ایده: تکنیک دوبرابر کردن

مقدار دهی اولیه: s: نقطه ی اول؛ t: نقطه دوم؛ width=0

اضافه کردن نقطه p:

w = max( w, width(triangle(s,t,p)) )

if ||s-p|| > 2.||s-t|| then t = p

این روش در واقع اصلاح شده ی همان روش پیدا کردن دورترین نقطه از st است ولی چون آن الگوریتم 2 بار داده ها را می دید برای مدل جویبار داده مناسب نبود.

شرطی که در خط دوم الگوریتم است برای اصلاح st مورد استفاده در مرحله بعد است و جواب این مرحله همان w است که در خط اول به دست می آید.

تحلیل:

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

dist(p, line(s,ti)) <= 3w

اثبات:

area of triangle(s,p,ti) = dist(p, line(s,ti) ) * ||s-ti|| = dist(s, line(p,ti)) * ||p-ti|| (1)

line 1 alg'm ==> dist(s, line(p,ti)) <= w (2)

(1),(2) ==> dist(p, line(s,ti) ) * ||s-ti|| <= w*||p-ti|| (6)

triangle inequality ==> ||p-ti|| <= ||p-s||+||s-ti|| (3)

line 2 alg'm ==> ||s-p|| <= 2*||s-ti|| (4)

(3),(4)==> ||p-ti|| <= 3*||s-ti|| (5)

(6),(5) ==> dist(s,line(p,ti)) *||s-ti|| <= w*3*||s-ti||

==> dist(s,line(p,ti)) <= 3*w

(

* اثبات عرض مثلث

تقریب هسته ای که قبلا حساب کرده بودیم، سه حالت دارد که هر بار نسبت دو ضلع را بررسی می کنیم و در بین همه ی این حالت ها نسبت عرض محاسبه شده و جواب حداکثر 3 برابر است.

)

محاسبه تقریب بعد از به روز رسانی

dist(p, line(s,t(i+1)) ) <= dist(p, line(s,ti) ) + dist( p^, line(s,t(i+1)) )

چون خط عمود از p^ (که تصویر p روی line(s,ti) است)  به line(s,t(i+1)) با خط عمود از ti به این خط موازی است، طبق تالس داریم:

<= dist(p,line(s,ti))+||s-p^||/||s-ti|| * dist(ti, line(s,t(i+1))

line 1 alg'm ==>

<= dist( p,line(s,ti) ) + ||s-p^||/||s-ti|| *3*w_opt_i

فاصله ی عمودی از هر فاصله ی دیگری کمتر است

<= dist( p, line(s,ti) ) + ||s-p||/||s-ti|| *3w_opt_i (1)

line 2 alg'm ==> ||s-p|| > 2*||s-ti|| ==> ||s-t(i+1)|| > 2*||s-ti|| (2)

(1),(2) ==> dist(p, line(s,t(i+1)) ) <= dist(p, line(s,ti)) + 2*3*w_opt_i

==> w_alg_(i+1) <= w_alg_i+6*w_opt_i

==> w_alg_(i+1)  <= w_alg_0 + 2*3*w_opt_1+...+2*3*w_opt_i

proof of part 1 (w_alg_0 <= 3w_opt) ==> w_alg <= 3w_opt+2*3*w_opt_1+...+2*3*w_opt

line 2 alg'm (update) ==> 2*w_opt_i <= w_opt_(i+1)

==> w_alg <= 3w_opt+(..+1/4+1/2+1+2)*3w_opt <= 15w_opt

مقدار درست آن 18 است که با تحلیل بهتر به دست می آید اما تا همینجا به تقریب 30 می رسیم. (؟؟)

---------------

الگوریتم 3: تقریب عرض نقاط در مدل جویبار با استفاده از هسته ی گستره نقاط در دو بعد

ایده: تکنیک دو برابر کردن

s=نقطه اول، t=نقطه دوم

اضافه کردن نقطه p:

0- خطوط توری عمود بر st را با فاصله ی epsilon*||s-t|| رسم کن.

1- نقطه p را به نزدیک ترین خط توری رند کن.

2- تنها نقاط مینیمم و ماکسیمم را روی هر خط نگه دار.

3- اگر ||s-p|| >= 2||s-t است آنگاه t=p و خطوط توری را دوباره رسم کن و نقاط فعلی را دوباره رند کن.

تحلیل:

فضای حافظه : O(1/epsilon)

ضریب تقریب:

هر قدم رند کردن a.p را به اندازه epsilon*w_s{s,ti} <= epsilon*w_a(P_ تغییر می دهد.

بعد از log(1/eplsilon) گام رند کردن،

||s-p|| < epsilon* ||s-ti||

پس p روی خط توری گذرنده از s می افتد. (اولین خط توری)

هر قدم رند کردن a.p را به مقدار زیر تغییر می دهد:

<= L / ||s-ti|| * w_a(s,ti) <= ||s-p||/||s-ti|| w_a(P)

که L فاصله ی بین خط توری گذرنده از s و خط گذرنده از sp است.

{فکر کنم خط توری مرحله جدید و قبلی}

total error <= O(epsilon lg 1/epsilon)*w_a(P)+w_a(P)*epsilon*(1+1/2+...) <= O(epsilon lg 1/epsilon) w_a(P)

space: O(1/epsilon lg 1/epsilon)

بهبود این زمان ها موجود است.

دورترین همسایه، درخت پوشای ماکسیمم و مسائل مرتبط در ابعاد بالا

Agarwal, Matousek, and Suri (1991) – rounding the directions

چکیده: الگوریتم تصادفی با زمان متوسط

O(m^2/3 n^2/3 log^4/3 m + m log^2 m + n log^2 n)

برای محاسبه ی دورترین همسایه های دو-رنگی بین n نقطه قرمز و m نقطه آبی در E^3 می دهیم. الگوریتم می تواند برای محاسبه ی دورترین همسایه ها یا دورترین همسایه های خارجی n نقطه در E^3 در زمان متوسط O(n^4/3 log^4/3 n) به کار رود. با استفاده از این رویه ها به عنوان اجزای سازنده، می توانیم درخت پوشای ماکسیمم اقلیدسی یا افراز دو مجموعه ای با کمترین قطر برای n نقطه را در E^3 در زمان متوسط O(n^4/3 log^7/3 n) به دست بیاوریم. بهترین زمان قبلی O(n^3/2 log^1/2 n) بود. الگوریتم ما می تواند به ابعاد بالا تعمیم یابد.

همچنین ما الگوریتمهای تقریبی سریع و ساده برای این مسائل ارائه می دهیم. این الگوریتم های تقریبی جوابهایی می سازند که مقدار واقعی را با دقت e تقریب می زنند و در زمان O(n e^(1-k)/2 log n) یا O(n e^(k-1)/2 log^2 n) در فضای k-بعدی حل می شوند.

مقدمه:

در این مقاله مسائل را در فضای اقلیدسی E^k برای تعداد ابعاد ثابت k حل می کنیم. الگوریتم کارایی برای مسائل زیر ارائه می دهیم:

1- همه ی دورترین همسایه ها: یک مجموعه S از n نقطه در E^k داده شده است، برای هر نقطه p عضو S نقطه ی q عضو S را طوری پیدا کنید که d(p,q) >= d(p,q') باشد (به ازای هر q' عضو S)؛ به q دورترین همسایه p می گویند.

2- دورترین همسایه های دو-رنگی: مجموعه R از n نقطه قرمز و مجموعه B از m نقطه آبی در E^k داده شده اند. برای هر نقطه r عضو R، نقطه ی b عضو B را طوری پیدا کنید که d(r,b) >= d(r,b') باشد (به ازای هر b' عضو B)؛ در این صورت به b دورترین همسایه رنگی r می گویند.

3- دورترین همسایه خارجی: مجموعه S از n نقطه در E^k و افرازهای آن S1,S2,...,Sm داده شده است، برای هر p عضو S اگر p عضو Si است، نقطه ی q عضو S-Si را که d(p,q) >= d(p,q') برای همه ی q' عضو S-Si برقرار باشد؛ q را دورترین همسایه خارجی p می نامیم.

4- درخت پوشای ماکسیمم اقلیدسی (EMXST): مجموعه S از n نقطه در ٍE^k داده شده است، درخت پوشای S که یالهای آن ماکسیمم فاصله بین همه ی درخت های پوشا را دارند، که طول هر یال فاصله ی اقلیدسی بین نقاط دو سر آن است را محاسبه کنید.

5- افراز دو مجموعه ای با مینیمم قطر: مجموعه S از n نقطه در E^k داده شده است، S را به دو مجموعه افراز کنید طوری که ماکسیمم بین قطر این دو مجموعه نقطه مینیمم شود.

مساله محاسبه همسایه (دورترین، نزدیک ترین، یا میانی) یک مساله اصلی در هندسه محاسباتی است که کاربردهای زیادی دارد. اما مساله ی همه ی نزدیک ترین همسایه در E^k می تواند به صورت بهینه در O(n log n) حل شود، هیچ الگوریتمی با چنین کارایی برای دورترین همسایه به ازای k>= 3 نیست. کاربردهای زیادی به نسخه های دو-رنگی و خارجی هم نیاز دارند. برای این دو مساله هم در k>=3 جواب بهینه نداریم. برای زوج قطر مساله در O(n^ (2-2/(k/2+1+gamma)) برای n نقطه در k بعد حل شده است، اما الگوریتم داده شده قابل تعمیم به دورترین/نزدیک ترین همسایه نیست. بهترین الگوریتم فعلی برای دورترین همسایه در سه بعد در زمان O(n^3/2 log^1/2 n) کار می کند. در این مقاله یک الگوریتم بهتر ولی تصادفی برای دورترین همسایه ها و مسائل مربوط به آن برای سه بعد و ابعاد بالا می دهیم.

...

2- محاسبه دورترین همسایه

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

2-1- الگوریتم برای حالت نقاط آبی زیاد و نقاط قرمز کم

به صورت تصادفی زیرمجموعه ای m/4 عضوی از نقاط آبی انتخاب می کنیم و مجموعه نقاط قرمز را به دو مجموعه n/2 عضوی افراز می کنیم و مساله را برای این زیرمساله ها حل می کنیم. به ازای نقطه قرمز iام و دورترین همسایه آبی آن b'i تعریف می کنیم: Si را توپ به مرکز نقطه قرمز و شعاع فاصله قرمز و آبی می نامیم و S'_i را خارج این توپ تعریف می کنیم. چون b'i دورترین همسایه ri بوده است، پس B' درون همه ی توپ های به مرکز نقاط قرمز می افتد و دورترین همسایه ri در B یا b'i است یا در S'i می افتد. پس نقاط اشتراک Si ها جواب ما نیستند.

...

--------------

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

مرجع هندسه محاسباتی پیشرفته

خودم این را پیدا کرده بودم اما نمی دانم چرا قبلا نگذاشته بودمش.

دریافت
حجم: 409 کیلوبایت

هسته سریع برای مدل جویبار داده (تیموتی چان)

http://graphics.stanford.edu/courses/cs468-06-winter/Slides/eugene_faster_core-set_winter.pdf

جلسه پنجم

مدل جویبار داده (Streaming Model)

تعریف: یک الگوریتم stream الگوریتمی است که ورودی را در یک عبور (pass) می بیند و حافظه محدود دارد. {بهتر است بگوییم جویبار داده نامحدود است!}

*حل مساله قطر با جویبار داده

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

برای یک بعد: با محاسبه مینیمم و ماکسیمم با O(1) حافظه به دست می آید و با یک pass انجام پذیر است.

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

پس برای بیشتر از یک بعد نمی توانیم الگوریتم جویبار داده ی دقیق بدهیم.

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

روش 0 (پیدا کردن دورترین نقطه از یک نقطه): O(1) حافظه می خواهد و در یک عبور امکان پذیر است.

روش 1 (پیدا کردن دورترین نقطه از یک نقطه و دورترین نقطه از آن): به دو عبور نیاز دارد. (نمی شود)

روش 2 (توری): نمی شود چون برای به دست آوردن تقریب اندازه خانه های توری (که گفتیم با یکی از الگوریتم های قبلی انجام می شود) به 2 عبور نیاز خواهد داشت.

روش 3 (رند کردن نقاط در جهت های مختلف): می شود چون بیشتر از یک عبور نیاز نداریم. حافظه ی O(1/epsilon^((d-1)/2)) می خواهد.

* مزیت الگوریتم 0 این است که در ابعاد بالا هم کار می کند، اما الگوریتم 3 نمایی است.

---------------------------------

*آیا می توان مساله نزدیک ترین دو نقطه را در مدل جویبار داده حل کرد؟ خیر، حتی نمی توان تقریب زد.

*آیا می توان مساله عرض نقاط را با این حل کرد؟ بله، با همان coreset گستره نقاط (extent)

*محاسبه عرض نقاط

الگوریتم 1: یک epsilon-هسته از نوع گستره نقاط پیدا کن

ایده: ادغام و کاهش (به آن روش لگاریتمی هم می گویند.)

اضافه کردن نقطه:

1) یک هسته شامل مجموعه تک عضوی {p} بساز. (سطح 0)

2) تا وقتی 2 هسته ی S1 و S2 به ترتیب برای مجموعه نقاط P1 و P2 وجود دارند و در یک سطح هستند:

2-1) اپسیلون هسته ی S که اجتماع S1 و S2 است محاسبه کن.

2-2) S را به عنوان هسته ی P1 U P2 در سطح i برچسب بزن. {حس می کنم اینجا باید i+1 باشه!}

2-3) S1 و S2 را حذف کن.

{جواب هم باید هسته ای باشه که در مرحله ی آخر =بالاترین سطح درخت باقی می ماند.}

دلیل نام گذاری این است که مجموعه نقاط هم سطح را ادغام می کند و وقتی برای سطح بالاتر هسته ساخت هسته های سطح پایین تر را حذف می کند.

{البته فکر کنم کاهش منظور همان ساختن هسته و کاهش نقاط است.}

تحلیل

تعداد سطح ها: O(log n)

فضای لازم: O(1/epsilon^d lg n) (اصطلاحاً polylog( n))

زمان: O(1/epsilon^d n)

( ضریب 1/epsilon^d از اندازه ی هسته می آید. lg n از عمق درخت. n از تعداد ادغام ها= کل گره های درخت)

دلیل حفظ ضریب تقریب هسته (هنگامی که دو هسته ادغام می شود) این است که هسته های قبلی نقاط مجزا داشته اند:

*اگر S1 یک اپسیلون-هسته برای P1 و S2 یک اپسیلون-هسته برای P2 باشد، S1 U S2 یک اپسیلون-هسته برای P1 U P2 است.

*اگر S یک اپسیلون-هسته برای Q باشد و Q یک اپسیلون پریم-هسته برای P باشد، آنگاه S یک (اپسیلون+اپسیلون پریم) - هسته برای P است.

(چون ضریب تقریب های آنها جمع می شود.)

در کل یک O(epsilon* log n)-هسته به دست می آید. اپسیلون را طوری تعیین می کنیم که log n حذف شود:

epsilon' = epsilon/lg n

و با این اپسیلون جدید هسته ها را به دست می آوریم.

فضای کل لازم O( 1/epsilon^(d-1) log^d n) است.

این مدل برای جویبار داده قابل استفاده هست اما می خواهیم مستقل از n کنیم.

جلسه چهارم

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

*هسته ی گستره ی نقاط (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}

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

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

جلسه سوم

عرض نقاط

مجموعه P از n نقطه در فضای d بعدی داده شده است، کمترین فاصله بین دو ابرصفحه موازی را پیدا کنید که همه ی نقاط بین دو ابر صفحه بیفتند.

= پیدا کردن ابرصفحه ای که فاصله ی دورترین نقطه از آن مینیمم شود. (صفحه ی بین دو ابرصفحه ی موازی قبل این صفحه است.)

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

2بعد: anti-podal pair و پوسته محدب O(nlogn)

3بعد: تصادفی Agrawal,Sharir 1995 زمان ((O(n^(3/2+epsilon

4 بعد و بیشتر: O(n^ceil(d/2))

تعریف ریاضی مساله:

w* = min (1/ sqrt(n1^2+n2^2+...+nd^2) )

s.t. h <= x1*n1+...+xd*nd <= h+1

(parallel planes: x1*n1+...+xd*nd=h, x1*n1+...+xd*nd=h+1)

(variables: (n1,...,nd,h) )

این یک LP نیست چون تابع آن خطی نیست، اما برنامه نویسی محدب است.

زمان حل: O(n^ceil((d+1)/2))

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

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

1- الگوریتم Duncan, Goodrich, Ramus 1997

ایده: رند کردن نقاط با استفاده از جهت و محاسبه عرض کج؟ (skewed width)

1) مجموعه جهت ها را بساز. O(1/epsilon^(d-1)) جهت برای حفظ حداکثر زاویه بردار دلخواه با این جهات.

2) در هر کدام از جهت های قسمت 1، عرض کج را در آن جهت حساب کن. (عرض کج = عرض نقاط در آن جهت)

نحوه ی محاسبه ی عرض کج: یک LP با d+1 متغیر است که d تای آن مربوط به ابرصفحه ی وسط دو صفحه (به تعریف مساله نگاه کنید) هستند و متغیر دیگر مربوط به حداکثر فاصله یک نقطه از این ابرصفحه است که هدف LP هم مینیمم کردن آن است.

با توجه به اینکه نرمال صفحه بردار a (بردار جهت) است که در مرحله ی اول الگوریتم به دست آمده است، نمی دانم چرا در جزوه d+1 متغیر در نظر گرفته شده، باید همان 1 متغیره باشد!

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

#directions * LP(#points)

O(1/delta^(d-1) * n)

*ضریب تقریب:

width_OPT <= width_ALG <= width_OPT/cos(delta)

factor = 1/cos(delta)

1/(1-x) = 1+x+x^2+... >= 1+x

cos(delta) = 1-2*sin^2(delta/2) = 1-2(delta-delta^3/3+...)^2 <= 1-2*delta^2

x=2*delta^2

1/cos(delta) >= 1+2*delta^2

epsilon = 2*delta^2

factor = 1+epsilon

2- الگوریتم Agarwal, Har-peled, vardarajan 2004

ایده: رند کردن نقاط با توری غیر یکنواخت + دوران یافته + مقیاس شده (scaling)

*مساله کلی تر: برای همه ی جهت ها تقریب را به دست بیاوریم: با کمک یک زیر مجموعه از نقاط:

زیر مجموعه ای از نقاط را پیدا کنید که به ازای هر بردار یکه a داشته باشیم:

width_a (all points) >= width_a (subset) >= width_a(all points) *(1-epsilon)

width_a (points) = max_p,q_points (a.(p-q))

به این یک extent (گستره) از نقاط می گویند و یک اپسیلون-هسته است. (epsilon-coreset)

*پیدا کردن هسته با اندازه ی ثابت

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

s: هر نقطه ی دلخواه از مجموعه نقاط ورودی (P)

t: دورترین همسایه s

u: دورترین نقطه از پاره خط st

عرض نقاط: عرض سه نقطه ی قبل

زمان الگوریتم: O(n) که n تعداد نقاط است.

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

چون در طرف دیگر خط st هم می تواند نقطه باشد، جواب الگوریتم را دو برابر عرض نقاط هسته می دهیم.

اشکال جزوه: عرض بهینه را بیشتر از عرض به دست آمده از الگوریتم گرفته که غلط است. (مساله کمینه سازی بوده است.)

الآن باید تقریب هسته را در بیاوریم و در تقریب الگوریتم (=2، چون جواب حداکثر دو برابر عرض نقاط است: همه یک طرف خط st باشند) ضرب کنیم.

تقریب هسته:

هسته ی فعلی ما دو خط موازی اند که یکی از آنها امتداد st است و دیگری خط موازی آن است که از u می گذرد. چون همه ی نقاط باید در فاصله بین این دو خط باشند، مثلث ust در همه ی این هسته ها وجود دارد. 

||u-t|| <=||s-t||+||s-u|| (triangle inequality) <= 2.||s-t|| (t = farthest point from s)

width_ALG*||s-t|| = width_coreset*||u-t|| <=2.||s-t||.width_coreset

==> width_ALG <= 2.width_coreset

پس تقریب الگوریتم 4 است.

جلسه دوم

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

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) )

coreset: تقریب گستره نقاط

http://graphics.stanford.edu/courses/cs468-06-winter/Slides/nikola_approx_extent_measures_winter.pdf