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

پیدا کردن نقطه (point location): یک گراف هندسی داریم، آن را طوری پیش پردازش کنید که بتوانیم کوئری های به شکل پیدا کردن فیس شامل یک نقطه را زود جواب بدهیم.

• یک بعدی:

یک سری بازه روی محور اعداد داریم. (مجزا) می خواهیم ببینیم نقطه در کدام بازه است؟

بازه ها را مرتب می کنیم و باینری سرچ می زنیم! :)

زمان پیش پردازش: nlogn (مرتب کردن)

فضا: n (لیست مرتب شده)

زمان کوئری: logn (باینری سرچ)

با قضیه ben ore ثابت می شود که از logn کمتر نمی شود نقطه را پیدا کرد. (املای اسم طرف رو مطمئن نیستم! :دی)

• دو بعدی:

به جای اینکه خود مساله را حل کنیم، صورت ساده تری از آن را حل می کنیم که جواب آن مساله ی قبلی را هم می دهد:

مجموعه ای از پاره خط های مجزا داریم که می خواهیم طوری آن را پیش پردازش کنیم که به کوئری های به شکل اولین خط بالای یک نقطه ورودی در زمان کم جواب بدهیم.

روش های 0-2 بر مبنای تقسیم صفحه به نوارهای عمودی از سر پاره خط ها هستند. (slab) اما روش 3 بر مبنای ذوزنقه بندی و روش 4 بر مبنای مثلث بندی هستند. (از سر پاره خط تا قطع کردن پاره خط بعدی)

0- روش Dobkin و Lipton

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

جواب دادن به کوئری: روی x نقطه باینری سرچ می زنیم تا نوار شامل آن را پیدا کنیم. بعد روی y آن باینری سرچ می زنیم تا y را پیدا کنیم.

زمان پیش پردازش: O(n2): اگر بدون sweep انجام بدهیم چون O(n) تا ناحیه (سر پاره خط) داریم و مرتب کردن خطوط هر ناحیه O(nlogn) زمان می خواهد کلا می شود O(n^2logn) اما اگر sweep را یادتان باشد، از روی ناحیه قبلی ناحیه جدید به دست می آید و در نتیجه زمان آن فقط زمان کپی کردن لیست قبلی O(n) می شود برای هر ناحیه که کلا چون n ناحیه است می شود O(n^2).

زمان جواب دادن به کوئری: O(nlogn) (باینری سرچ)

فضای مورد نیاز: O(n^2) : چون n تا لیست به طول n داریم.

1- روش تقسیم و حل

از segment tree استفاده می کنیم.

زمان: nlogn*logn

زمان کوئری: logn*logn

فضا: nlogn

از fractional cascading هم استفاده می کنیم.

زمان: nlogn

زمان کوئری: logn

فضا: n

2- persistent search tree (درخت جستجوی پایدار)

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

زمان: nlogn (زمان ساخت درخت اول است. در مرحله های بعد فقط یک مسیر در logn ساخته می شود.)

زمان کوئری: logn

فضا: nlogn

ایده: path copying

درخت جدید را کامل نمی سازیم و فقط مسیری که پاره خط جدید به آن اضافه شده است را می سازیم و بقیه را به زیر درخت های درخت قبلی با اشاره گر وصل می کنیم.

زمان: nlogn

زمان کوئری: logn

فضا: n

3- تصادفی افزایشی

ایده: سلسله مراتب ذوزنقه بندی

(قبلا در نمونه سوالهای هندسه محاسباتی توضیح دادم ذوزنقه بندی را.)

الگوریتم:

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

تحلیل:

تعداد راسهای ذوزنقه بندی: 2n+2*(2n)+4 = تعداد دو سر پاره خط ها*2 (تقاطع خطوط دو سر پاره خط ها)+ 4 گوشه ی مستطیل+ تعداد دو سر پاره خط ها

تعداد ذوزنقه ها: 3n+1 = پاره خط اول 4 ناحیه می سازد، اما هر کدام از بعدی ها یک ناحیه کم می کنند و سپس 4 ناحیه اضافه می کنند. پس می شود:

4+(n-1)*(4-1) = 3n+1

تعداد پاره خطهای اطراف هر ذوزنقه: کمتر از 4n

زمان کوئری:

Q(n) = Q(n-1)+O(1/n)

Q(n) = O(logn)

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

فضای حافظه الگوریتم:

تعداد ذوزنقه های ساخته شده در هر مرحله O(1) است و کلا n مرحله داریم پس کلا O(n) فضا لازم است.

زمان الگوریتم: (پیش پردازش)

در هر مرحله ی الگوریتم یک کوئری زده می شود که logn زمان می برد و ساخت گراف جهت دار هم به اندازه ی تعداد راسهای آن یعنی O(n) زمان می برد.

پس کلا زمان O(nlogn) می برد. (متوسط)

4- روش هرس و جستجو (prune and search)

فرض می کنیم شکل مثلث بندی شده است و به جای ذوزنقه بندی از مثلث بندی استفاده می کنیم.

الگوریتم: هر بار یک راس از مثلث بندی را حذف می کنیم، بعد چند ضلعی جدید را مثلث بندی می کنیم.

این کار را که بازگشتی انجام بدهیم، در قسمت اول به جایی می رسیم که فقط یک ناحیه است (ریشه گراف جهت دار؟!) و با برگشت به قسمت های قبلی و اضافه شدن راس و ساخته شدن مثلث ها گراف کامل می شود.