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

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

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

سوال خوشه بندی تو کتاب هندسه! :))

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

جواب:

2D range tree: درخت روی نقاط دو سر بازه ها که مینیمم هر دو برگ مقدار پدرشان است.

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

جواب:

priority search tree:

تمرین های کتاب (ادامه)

جواب تمرین های خودمون

مروری بر مشخصات درخت ها

segment tree

build: O(nlogn)

storage: O(nlogn)

query: O(logn+k)

----------------------------------

interval tree

build: O(nlogn)

storage O(n)

query: O(logn+k)

----------------------------------

range tree

build: O(nlogn)

storage: O(n)

query: O(logn+k)