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

1- الف) یک چندضلعی با n راس و h حفره k راسی داریم. تعداد مثلثهای مثلث بندی آن چقدر است؟

ب) یک ذوزنقه بندی داریم که در آن پاره خط ها متقاطع هستند (مجزا نیستند)، تعداد ذوزنقه ها و مثلث ها چقدر است؟ (ناحیه ها)

ج) در یک kd tree حداکثر ناحیه هایی که یک خط آنها را قطع می کند چندتا است؟

د) یک مثال کلی و قابل تعمیم بزنید که نمی توان چند ضلعی دارای حفره را با floor(n/3) نگهبان (مساله art gallery) پوشش داد.

2- الف) چند ضلعی ستاره شکل (قبلا توی وبلاگ گفته شده)

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

3- range tree

الف) برای یک مستطیل با اضلاع موازی y=x و y=-x

ب) برای یک مثلث با دو ضلع موازی محورهای مختصات و یک ضلع موازی y=-x

ج) برای مجموعه n خط که بخواهیم برای سه تایی های (t0,t1,t2)، خطوطی را برگردانیم که بالای (1,t0) و زیر (t1,1) و (2,t2) باشند. (جای مختصاتها را برعکس می نویسد شما درستش را بخوانید!)

LP

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

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

سوال هندسه

http://www.cs.tulane.edu/~carola/teaching/cs6463/fall06/homework/homework4.pdf

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

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

این یکی از سوالهای تمرین های همین سری خودمون بود، فقط یک فرق کوچک داده بود توش ولی ایده همین بود. جواب سوال (حالتهای چک کردن نبودن جواب را حذف کردم چون طولانی بود):

تحلیل:

دلیل d/(i-d) هم این است که d تا ابرصفحه جواب vi-1 را تعریف کرده اند و ما d تا از بین i تا صفحه را انتخاب کرده ایم، پس احتمال اینکه یکی از صفحه های جواب خارج از مجموعه انتخابی ما باشد انقدر می شود.

با استقرا روی تعداد ابعاد ثابت کرده است که اگر برای d-1 بعدی ثابت Cd-1 باشد، برای d بعدی ثابت Cd است که حداکثر d برابر ثابت قبلی است.

ب) بدترین حالت چیست؟ آن را تحلیل کنید و مثال بزنید.

بدترین حالت این است که هر بار صفحه هایی را انتخاب کنیم که جواب نباشند! برای مقدارش هم باید xi=1 باشد که در همان رابطه بالا بگذاریم جواب به دست می آید.

تعداد نقاط درون مثلث

priority search tree

سوالهای اسلایدها

ray shooting

سوال آخر تمرین آخر ترم قبلی ها. ( به TA ایمیل بزنم بگم که قبلی غلط بود! :)) )

سوالی که برای خودم پیش میاد اینه که چرا جواب تمرین های خودمون رو پیدا نمی کنم چک نمی کنم که یه وقت غلط نباشن؟ از دید بهینه سازی هم هدف من باید افزایش نمره ام باشه ولی متاسفانه در جهت افزایش ایده های خلاقانه است! :|

بقیه سوالها

بقیه سوالهایی که از کتاب Berk نبود از کتاب Rourke بود.

الآن خیلی دیره واسه فهمیدن اینها.

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

http://www.cs.tulane.edu/~carola/teaching/cs6463/fall06/homework/homework5.pdf

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

تبدیلش میشه این (به نظرم):

z=x+y

کاربردهای kd tree

https://www.cs.umd.edu/users/meesh/420/Notes/MountNotes/lecture17-quadkd.pdf

1- پیدا کردن یک نقطه

2- پیدا کردن k نزدیک ترین همسایه یک نقطه

3- پیدا کردن نقاطی که کاملا درون یک شکل می افتند (range query با شکل دلخواه)

4- پیدا کردن اولین شیئی که یک شعاع به آن می خورد. ray shooting

خوب هیچ کس توضیح بیشتری نداده. چهارمی تمرین سال قبلی ها بوده و سومی سوال امتحانشون. :|