جلسه ششم

الگوریتم 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)

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