جواب تمرین هندسه محاسباتی پیشرفته (تمرین ۲)

جوابهای خودم اند.

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

ب) قسمت اول: نسبت مساحت قسمتی که مرکز دایره می‌تواند در آن قرار بگیرد به کل خانه را حساب می‌کنیم و این احتمال مورد نظر است.

قسمت دوم: با قسمت قبل و به دست آوردن i با کمک شرط خاتمه به احتمال مورد نظر می‌رسیم.

ج) احتمال مورد نظر کمتر از مکعب شامل دایره به مرکز نقطه کوئری و شعاع بهینه است. نسبت حجم توپ و مکعب شامل توپ ثابت است پس احتمال مورد نظر از مرتبه نسبت مکعب محیطی توپ و مکعب خانه داده شده است.

د) جستجوی دودویی+اجرای الگوریتم

ه) جمع مقادیر قسمت قبل است. رابطه‌ی آن قبلاً آورده شده است.

۲- الف) حداکثر ۴ نوار اطراف (راست چپ بالا و پایین) خطا ایجاد می‌کنند پس با قرار دادن ۴*اپسیلون به جای اپسیلون به جواب می‌رسیم. (حکم را در تعداد نقاط هر خانه ضرب کنید.)

ب) روش merge & reduce را به کار ببرید. لگاریتمی بودن را با فرض داشتن n حل کنید.

ج) اپسیلون خلاصه را بسازید و طبق قسمت ب تقریب به دست می‌آید.

*مهلت تحویل تمرین: سه‌شنبه

تمرین سری دوم هندسه پیشرفته (راهنمایی)

مرجع: http://en.wikipedia.org/wiki/Summation

مروری بر آنچه گذشت.. (هندسه محاسباتی پیشرفته)

۱- تقریب قطر

*تقریب ضریب ثابت: استفاده از نامساوی مثلث و ... برای به دست آوردن تقریب ثابت+تقریب قطر با دورترین نقطه از یک نقطه

*رند کردن ورودی: نقاط ورودی را به نزدیک ترین رأس توری رند می‌کردیم.

*رند کردن جهت‌ها: یک سری شعاع با فاصله یکسان می‌کشیدیم و در راستای آنها جواب را حساب می‌کردیم. + directional width

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

*دیاگرام ورونوی گسسته: یک توری می‌ساختیم و فقط دورترین نقطه به نقاط توری را پیدا می‌کردیم.

۲- تقریب عرض

*رند کردن در جهت‌ها و LP: رند کردن جهت‌ها و استفاده از LP در مرحله‌ی آخر به جای یک الگوریتم دیگر+ساخت توری تجانس یافته در یک جهت و رند کردن نقاط در آن جهت

*یک تقریب ثابت ساده برای عرض: دورترین نقطه نسبت به پاره خط واصل یک نقطه دلخواه و دورترین نقطه به آن

*اپسیلون-هسته: ساخت هسته با روش افزایشی روی ابعاد و تصویر کردن

*روش سریعتر برای محاسبه هسته: تبدیل آفین (ترکیب خطی برداری)‌+رند کردن به رئوس توری

-موارد دیگر: +دیاگرام ورونوی گسسته +تقریب هسته extent برای همه‌ی توابعی که به پوسته محدب وابسته اند.

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

* روش لگاریتمی برای حفظ هسته: هسته دو مجموعه نقطه را به هسته برای اجتماع نقاط تبدیل می‌کند.(برای گستره نقاط)+روش لگاریتمی: ادغام (دو هسته) و کاهش (حذف هسته‌های قبلی)

*روش دوبرابر کردن برای حفظ هسته: نقاط را به صورت افزایشی اضافه می‌کنیم، هرجا تقریب از ۲ بیشتر شد به هسته نقطه اضافه می‌کنیم.

*هسته تقریبا بهینه در مدل جویبار داده:‌ دوبرابر کردن+رسم مجدد توری با اپسیلون جدید در هر مرحله و محاسبه جواب توری جدید از روی قبلی

۴-کوچکترین توپ محیطی

*الگوریتم جویبار داده ساده با ضریب ۳/۲: مرکزهای متحرک (توپ‌های محیطی)

*الگوریتم تکراری +شمای تقریبی (تقریب ۱+اپسیلون): روش مرکزهای متحرک با اضافه شدن دورترین نقاط به جواب قبلی به صورت افزایشی

*هسته با اندازه یک بر اپسیلون برای هر بعدی: بهبود تحلیل روش قبل با محاسبه‌ی حداکثر تغییر در هر مرحله

5-نزدیک‌ترین همسایه تقریبی

*روش جستجوی شعاع ثابت (دو روش ساده مبتنی بر توری): فقط خانه‌های توری که نقطه دارند نگه دار و هنگام کوئری خانه‌های اطراف یک نقطه را به دست بیاور. روش۲: خانه‌های توری اطراف هر نقطه را نگه دار و هنگام کوئری یک دایره شامل نقطه کوئری را از بین همسایگی‌های نقاط برگردان.

*استفاده از درخت چهارتایی (نسخه‌های فشرده و متوازن):‌ توری سلسله مراتبی برای حل مشکل شعاع متغیر. استفاده از تقاطع دایره کوئری با خانه‌های توری‌های درخت چهارتایی

*کاهش ابعاد با لم JL: تصویر کردن تصادفی و استفاده از توری

۶-تجزیه زوج خوب از هم جدا شده (WSPD)

*تجزیه زوج از هم جدا شده:‌ برای ساخت آن از درخت چهارتایی فشرده استفاده می‌کنیم و تا وقتی که فاصله‌ی دایره‌های متناظر مجموعه نقاط به نسبت شعاع بر اپسیلون نرسیده است مجموعه نقاط را تقسیم می‌کنیم و در درخت پایین می‌رویم.

*کاربرد آن در پوشاننده‌ها و درخت پوشای کمینه‌ی اقلیدسی: نسبت کوتاهترین فاصله در گراف به فاصله اقلیدسی حداکثر t باشد به گراف t-spanner می‌گوییم. اگر از زوج‌های خوب جداشده هر دو نقطه را به هم وصل کنیم گرافی که به دست می‌آید ۱+اپسیلون پوشاننده است. درخت پوشای کمینه اقلیدسی را هم با اجرای الگوریتم درخت پوشای کمینه روی پوشاننده می‌توان به دست آورد. (با الگوریتم‌های معمولی MST مثل prim و kruskal)

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

جواب تمرین ها تو خود کتاب هست! (ته کتاب)

فصل 3 vladlen

کاربردهای اپسیلون-نت

*arrangement & point location

-مکان یابی نقطه در arrangement

مکان یابی را به صورت شمارش تعداد ابرصفحه هایی که نقطه کوئری زیر آنهاست، تعریف می کنیم.

ساختمان داده ای که به کار می بریم یک درخت است که در هر راس آن یک زیرمجموعه از ابرصفحه ها است. ریشه کل صفحه هاست. به ازای هر گره از درخت، به صورت بازگشتی زیردرخت آن را می سازیم. فرض کنید کلا n ابرصفحه داشته باشیم. اگر به ازای یک ثابت سراسری n0 بدانیم n<= n0 است این گره یک برگ است و بازگشت تمام می شود. در غیر این صورت ست سیستم (کل صفحات، صفحاتی که اشتراک یک d-simplex در صفحه اقلیدسی d بعدی دلتا با آنها تهی نباشد) می سازیم. این یک زیرسیستم از ست سیستم است که بعد VC آن حداکثر O(d^3 log d) است. پس بعد VC ست سیستم ما حداکثر O(d^3 log d) است که O(1) است چون d را ثابت فرض کردیم. پس قضیه اپسیلون-نت نتیجه می دهد که با نمونه گیری تصادفی در زمان O(n) می توانیم یک 1/r-نت بسازیم برای ست سیستم مان که اندازه اش O(r log r) است. آن را به simplex هایی با استفاده از روش بعد تجزیه می کنیم که به آن "bottom-vertex simplicial decomposition" می گویند.

منظور از تجزیه به simplex ها این است:

1) اجتماع آنها کل فضا را بدهد.

2) اشتراک دو به دوی آنها تهی باشد.

3) هر عضو از مجموعه صفحات منتخب با هر simplex انتخاب شده یا اشتراک تهی داشته باشد یا simplex زیرمجموعه آن باشد.

با استقرا روی تعداد ابعاد به دست می آید:

برای یک بعد خود arrangement جواب است. برای ابعاد بالاتر به ازای هر صفحه از مجموعه F می توانیم X|f و arrangement آن را در آن صفحه حساب کنیم. ...

* جستجوی تقاطع پاره خط ها

با point location و ساختمان داده مناسب می توان در O(n^(d+epsilon)) پیش پردازش (به ازای هر اپسیلون) و زمان کوئری O(log n) به آن جواب داد.

به ازای دو سر پاره خط صفحه ها به دو زیرمجموعه مجزای تقسیم می شوند که از زیر یکی و بالای دیگری می گذرند (و برعکس این!).

*جستجوی بازه ای

مساله simplex range searching : مجموعه P از n نقطه در صفحه اقلیدسی d بعدی داده شده است، می خواهیم P را طوری پیش پردازش کنیم و ساختمان داده ای بسازیم که به ازای simplex S کوئری d بعدی بتوانیم تعداد نقاطی از P را که در آن می افتند بشماریم. (یعنی اشتراک S و P)

با دوگان گرفتن حل می کنیم. یک simplex با d بعد را می توان به صورت تقاطع d+1 نیم ابرصفحه در نظر گرفت. حالا با دوگان گرفتن ابرصفحه به نقطه تبدیل می شود و مساله به مساله ی اول (مکان یابی نقطه) تبدیل می شود.

* جستجوی نزدیک ترین همسایه

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

argmin sqrt( sum_i_1_d(pi-qi)^2 )

(sqrt is monotone) ==> argmin sum_i_1_d (pi-qi)^2 = argmin sum_i_1_d (pi^2)-2sum(pi qi)+sum(qi^2)

(qi^2 is constant for all points: it's query point)

==> argmin (sum(pi^2)-2*sum(pi qi) )

f_p(x) = sum(pi^2) -2sum(pi xi)

این تابع یک ابرصفحه است. کوئری نزدیک ترین همسایه یک x برای تابع بالا می دهد و می خواهد نقطه ای که f_p(x) را مینیمم می کند پیدا کند. این معادل point location در دیاگرام کمینه سازی مجموعه همه ی fp ها است. (دیاگرام ورونوی)

همان کار قسمت اول را انجام می دهیم فقط به جای اینکه تجزیه را برای همه ی ناحیه ها انجام دهیم فقط برای ناحیه های زیر lower envelope انجام می دهیم.

زمان کوئری O(log n) و زمان پیش پردازش O(n^(ceil(d/2)+epsilon)) است.

فصل 2 هندسه پیشرفته vladlen

اپسیلون-نت و ابعاد VC

-اپسیلون نت

کاربرد در ساختارهای هندسی تصادفی

تابع X با احتمال m را در نظر بگیرید. اکثرا m یکنواخت است. یک مجموعه از زیرمجموعه X را F بنامید. (X,F) را یک سیستم مجموعه (set system) می نامند. (اگر X یک مجموعه متناهی باشد به آن ابرگراف هم می گویند.) یک اپسیلون-نت برای (X,F) مجموعه ای است که همه ی اعضای با m بیشتر از اپسیلون از مجموعه های F را شامل می شود.

مثال: یک set system متناهی (X,F) که در آن تعداد اعضای X برابر n است و تابع احتمال یکنواخت است (m(S) =|S|/n). یک 1/r-نت (برای r طبیعی مثبت) برای (X,F) زیرمجموعه N از X است که با همه ی اعضای F که حداقل n/r عضو دارند اشتراک ناتهی دارد.

اپسیلون-نت های کوچک برای ما جالب هستند. مخصوصا به ازای اپسیلون ثابت، می خواهیم یک اپسیلون-نت با اندازه ی ثابت پیدا کنیم! یعنی اندازه ی آن به اپسیلون وابسته باشد اما به set system وابسته نباشد. این همیشه ممکن نیست ولی معمولا ممکن است. برای توضیح کلاسی از ست سیستم ها نیاز به که اپسیلون-نت های کوچک دارند نیاز به تعریف VC-بعد داریم.

2.2. تعریف VC-بعد

VC-بعد یک پارامتر عددی برای ست سیستم است که نشان می دهد که سیستم چقدر خوش رفتار است. یک ست سیستم (X,F) و زیرمجموعه Y از X داده شده است محدود کردن F روی Y مجموعه ی F|y است که اشتراک مجموعه های F با مجموعه ی Y است.

تعریف: یک ست سیستم (X,F) و زیر مجموعه A از X  (تعریف بالا) را توسط F شکسته شده می نامیم اگر هر زیرمجموعه A اشتراک یک عضو F با A باشد؛ یعنی F|y = 2^A. بعد VC برای F بزرگترین زیرمجموعه از X است که با F شکسته می شود.

مثال: X را صفحه اقلیدسی (دو بعدی) و F1 را مجموعه همه ی چندضلعی های محدب در صفحه و F2 را مجموعه ی همه ی نیم صفحه ها فرض کنید. ست سیستم (X,F1) بعد VC بینهایت دارد. یک مجموعه A به دلخواه بزرگ از صفحه که محدب باشد در نظر بگیرید. هر عضو A' از A می تواند به صورت اشتراک A با یک چندضلعی محدب دیده شود.

اما ست سیستم (X,F2) تعداد بعد VC آن 3 است.

*تابع شکست

ماکسیمم تعداد اعضای F|y به ازای همه ی مجموعه های m عضوی از X را تابع شکست ست سیستم (X,F) به ازای m می نامند.

*اپسیلون نمونه

به ازای ست سیستم (X,F) ، یک زیرمجموعه N از X را اپسیلون نمونه برای (X,F) می نامیم اگر به ازای هر عضو F مثل S داشته باشیم: اختلاف نسبت اشتراک N و S به تعداد اعضای N و m(S) کمتر مساوی اپسیلون باشد.

*قضیه اپسیلون نمونه

به ازای ست سیستم (X,F) که dim(F) <= d که دی بزرگتر مساوی 2 و آر بزرگتر مساوی 2 که آر یک پارامتر است یک 1/r-نمونه برای (X,F) با اندازه ی حداکثر Cdr^2 ln r وجود دارد که C یک ثابت مطلق است.

فصل 1 هندسه پیشرفته vladlen

لینک فایل را قبلا گذاشته ام.

موضوعات فصل 1:

-ترکیب آفین و ترکیب محدب

تبدیل آفین sum(xi*ai) ها است که xi ها نقاط اند و ai ها ضریبهایی که جمع آنها 1 می شود.

ترکیب محدب ترکیبی است که در آن ai ها مثبت باشند. (در نتیجه هر کدام از 1 هم کمتر می شوند.)

وابستگی آفین: اگر یک نقطه را بتوان به صورت ترکیب آفین بقیه نوشت.

زیرفضای خطی: k-flat گذرنده از مبدا

-قضیه رادون (Radon)

یک مجموعه با d+2 نقطه را می شود به دو مجموعه افراز کرد که پوسته ی محدب آنها اشتراک نداشته باشد. (فضا d بعدی)

اثبات: وابستگی آفین

-قضیه هلی (Helly)

اگر n مجموعه محدب داشته باشیم که هر d+1 تای آنها متقاطع اند، همه ی آنها متقاطع اند.

اثبات: قضیه رادون

-قضیه Caratheodory

هر ترکیب محدب n نقطه یک ترکیب محدب از حداکثر d+1 نقطه از بین آنهاست. (در فضای d بعدی)

اثبات: وابستگی آفین و وابستگی محدب

زوج نقاط خوب جدا شده (WSPD)

تجزیه نقاط به زوج نقاط خوب جدا شده:

الگوریتم به دست آوردن پوشاننده (spanner) با WSPD:

زمان و حافظه ی الگوریتم های پوشاننده ها:

پوشاننده های هندسی

اسلاید آن را قبلا گذاشته بودم. (اسلاید دانشگاه یزد بود).

الگوریتم حریصانه ی اصلی جواب بهینه را حساب می کند اما دومی که زمان کمتری می برد O(n^2 log n) جواب بهینه را حتی برای حالت متریک حساب نمی کند.

به جای این کار می خواهیم به صورت زیر عمل کنیم:

تتا-گراف:

انواع تتا گراف:

تتا گراف پوشای سینک:

تتاگرافی است که درجه ی آن محدود است.

پوشاننده ی لیست پرشی:

تتاگرافی که قطر آن از مرتبه لگاریتم تعداد راسهاست.

زمان آن O(n log n) است و حافظه O(n) است.

اسلایدهای Agarwal

http://www.cs.duke.edu/~pankaj/slides/