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

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

ساختمان داده‌ای بسازید روی مجموعه نقاط d-بعدی P که به ازای نقطه کوئری داده شده نزدیک‌ترین نقطه را به آن برگرداند.

روش دقیق:

دیاگرام ورونوی و point location: پیش پردازش O(nlogn) و کوئری O(log n) و حافظه O(n) (دو بعدی)

برای ابعاد بالاتر حافظه O(n^ceil(d/2)) می‌شود یا می‌توان زمان کوئری را بیشتر کرد و O(n) کوئری (توان کمتر از ۱ بود) و O(n) حافظه داشت.

روش تقریبی:

تعریف مسأله: به ازای نقطه کوئری و شعاع همسایگی داده شده نقطه‌ای برگردانید که فاصله‌ی آن حداکثر ۱+اپسیلون برابر جواب بهینه باشد.

نسخه تصمیم گیری: اگر نقطه‌ای با مشخصات مورد نظر وجود داشت آن را برگردان و در غیر این صورت جواب بده وجود ندارد.

؟؟؟ فکر کنم نسخه‌ی تصمیم گیری فقط این باشه که این نقطه برای این مسأله جواب هست یا نه. (بله/خیر)

*روش ساده برای حالتی که شعاع همسایگی ثابت باشد:

یک توری با اندازه خانه‌های epsilon*r/sqrt(d) می‌سازیم و چک می‌کنیم که آیا هیچ خانه‌ی توری با توپ حول نقطه کوئری تقاطع دارد یا نه. روش: هشینگ

وقتی هش می‌کنیم یک مجموعه از خانه‌های توری برگردانده می‌شوند و باید کل آنها را بگردیم و نقاط آنها را چک کنیم که درون دایره می‌افتند یا نه و در بدترین حالت می‌شود که همه‌ی نقاط درون مکعب و خارج توپ بیفتند. اما چون از هر خانه فقط یک نقطه را نگه داریم مشکل قبلی حل می‌شود و زمان الگوریتم هم epsilon^-d می‌شود که تعداد خانه‌های توری است. دانستن شعاع هم برای ساختن توری لازم است.

*روش ساده ۲ برای حالتی که شعاع همسایگی ثابت باشد:

به جای پیدا کردن همسایه‌های نقطه کوئری، خانه‌های همسایه‌ی نقاط اصلی را پیدا کنیم و به ازای نقطه کوئری فقط باید چک کنیم که خانه‌ی شامل آن نقطه در همسایگی کدام مجموعه از نقاط آمده است. کوئری آن زمان O(1) می‌برد و فضای لازم آن O(epsilon^-d * n) است. چون به ازای هر خانه‌ی توری حداکثر n نقطه همسایه باید برای آن نگه داریم.