جلسه سوم

عرض نقاط

مجموعه 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 است.