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

نمونه گیری تصادفی تقریبی از ورودی را به ما می دهد و ممکن است گاهی به ما تقریب ویژگی که لازم داریم را هم بدهد اما وقتی این طور نباشد، می توانیم از مفهومی به نام هسته (coreset) استفاده کنیم که به طور خاص برای این تعریف شده است که تقریب یک ویژگی خاص را به ما بدهد.

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

مجموعه چاق خاصیت اپسیلون کرنل را حفظ می کند.

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

مقیاسهای گستره نقاط قابل اعتماد: توابعی هستند که هر ضریب دلخواهی از ضریب تقریب اولیه را برای هر اپسیلون کرنل بدهند.

مثال از مقیاس های قابل اعتماد: طول، عرض و ...

مثال از مقیاس های غیرقابل اعتماد: عرض کوچکترین زوج ابرکره شامل همه ی نقاط

به دست آوردن مقیاس های قابل اعتماد: ضریب تقریب را به ضریب داده شده تقسیم کرده و برای ضریب تقریب جدید جواب را به دست می آوریم!

به دست آوردن مقیاسهای غیر قابل اعتماد: می توانیم با خطی سازی بسیاری از توابع را به توابع خطی تصویر کنیم و ارتباط بین توابع خطی و نقاط را به دست بیاوریم.

برای مساله ها و کاربردها به اسلاید مراجعه کنید.

۰ نظر

۰ ۰۹ اسفند ۹۲ ، ۱۵:۱۳

سپیده آقاملائی

آلفا دیدپذیری

(اول بابت اختراع یک کلمه ی جدید به خودم تبریک میگم! alpha visibility)

http://sharif.edu/~zarrabi/papers/swat-12/alpha-visibility.pdf

تعریف دیدپذیری:

در شکل بالا بعد از این از نقطه p زاویه هایی با فاصله 2pi/alpha رسم می شوند. و ...

پیدا کردن نقطه ای که بیشترین زاویه دید نسبت به یک پاره خط را دارد و از دو نقطه می گذرد = تقاطع کوچکترین دایره ی گذرنده از دو نقطه و پاره خط

...

۱ نظر

۰ ۰۹ اسفند ۹۲ ، ۱۴:۲۳

سپیده آقاملائی

گستره نقاط

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

*مجموعه آلفا-چاق!

* گام اول: تبدیل مجموعه نقاط با یک تبدیل خطی به یک مجموعه آلفا-چاق

* تقریب در عمل چاق کردن حفظ می شود: (گام دوم)

* ضریب تقریب فقط به تعداد ابعاد وابسته است. تعریف فاصله hausdorff

* الگوریتم ساختن مجموعه آلفا چاق با استفاده از توری

* الگوریتم دوم ساخت مجموعه آلفا چاق: رند کردن در جهت های مختلف (چندوجهی)

* الگوریتم سوم ساختن مجموعه آلفا چاق: سطح توری

* توضیح روش آخر

* تقریب توابع d-1 متغیره

* دوگان ابرصفحه و نقطه

* تبدیل به روابط خطی که مساله را تبدیل به محاسبه اپسیلون-تقریب ریشه چندجمله ای های متناظر می کنند. (مثال)

۰ نظر

۰ ۰۹ اسفند ۹۲ ، ۱۳:۴۰

سپیده آقاملائی

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

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)

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

۰ نظر

۰ ۰۹ اسفند ۹۲ ، ۱۰:۲۲

سپیده آقاملائی

قدیمی ترین مطالب مطالب قدیمی تر جدیدترین مطالب مطالب جدید تر