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)
جواب:
الگوریتم:
1- تصویر بازه ها روی محور x را حساب می کنیم و یک درخت بازه روی آن می سازیم. (interval tree)
2- در هر نود درخت بازه ی ساخته شده، یک درخت محدوده (range tree) روی تصویر پاره خطها روی محور y (یک نقطه به ازای هر پاره خط) می سازیم.
3- کوئری را اول روی درخت بازه جواب می دهیم بعد روی درخت محدوده ی آن.
اثبات درستی:
در قدم اول [x,x'] را پیدا می کنیم و در قدم دوم بازه ی y را هم چک می کنیم.
زمان، پیش پردازش، کوئری:
برای درخت بازه ها: تعداد پاره خط ها = تعداد پاره خط های ورودی = n
برای درخت محدوده: تعداد نقاط = تعداد پاره خط های ورودی = n
1- پیدا کردن بازه های شامل یک نقطه: segment tree معمولی
2- پیدا کردن مساحت مستطیل ها (اجتماع بازه ها): semi static segment tree
3- پیدا کردن پاره خطهای متقاطع با یک پاره خط عمودی: augmented segment tree
(در هر گره یک BST نگهداری می کنیم که ترتیب خطهای عمودی را نگه می دارد. شبیه کاری که در سوئیپ می کردیم)
4- پیدا کردن مستطیل های شامل یک نقطه: multi-level segment tree
segment tree دو بعدی
Voronoi Diagrams and Delauney triangulations are data structures to reason about points and regions in space...
... not to be confused with the abstract, Paul Klee like work of Robert Delaunay.
http://www.cse.wustl.edu/~pless/546/
