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

پیدا کردن نقطه (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)

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

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

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

مساله های شبه LP

مساله های شبیه LP یا LP-type problem ها مساله هایی هستند که با همان ایده ی LP حل می شوند اما LP نیستند.

یکی از ایده هایی که به کار می رود ایده ی seidel است (تصادفی افزایشی).

مثال:

برای مجموعه ای از نقاط در صفحه کوچکترین دایره شامل همه ی نقاط را پیدا کنید.

پیدا کردن دایره: سه نقطه روی محیط آن یا دو نقطه روی قطر آن

الگوریتم تصادفی welz و Seidel

ایده: یک نقطه روی محیط را داریم.

تابع بازگشتی: circle(S,B) را تعریف می کنیم. در آن S مجموعه نقاط است و B نقاط روی محیط کوچکترین دایره ی محیطی این نقاط است.

شروع الگوریتم: circle(all points, empty)

حالت پایه: اگر S تهی بود یا B سه عضو داشت جواب را برگردان.

یک نقطه ی تصادفی از S را بردار و circle(S-{p},B) را صدا کن.

اگر نقطه ی p درون دایره افتاد همین جواب را برگردان، در غیر این صورت p روی محیط دایره می افتد و circle(S-{p},B U {p}) را برگردان.

( مثل استقرای قهقرایی :) )

زمان الگوریتم:

احتمال اینکه نقطه روی دایره بیفتند : 3 تقسیم بر n (شبیه 2 تقسیم بر n برای LP)

T(n,b) = T(n-1,b)+O(1)+3/n*T(n-1,b+1)

T(n,3) = O(1)

==>

T(n,2) <= T(n-1,1)+O(1)+T(n-1,3)=T(n-1,1)+O(1) ==> T(n,2) = O(n)

T(n,1) <= T(n-1,1)+O(1+3/n*n) ==> T(n,1) = O(n)

T(n,0) = T(n-1,0)+O(1)+3/n*T(n-1,1) <= T(n-1,0)+O(1)+3/n*O(n) = T(n-1,0)+O(1) ==> T(n,0) = O(n) 

تعمیم:

برای حالت d بعدی، زمان (d+1)!n به دست می آید.

بهتر از این هم هنوز حل نشده است. :)

الگوریتم های LP (قسمت دوم)

در قسمت قبل الگوریتم های قطعی را دیدیم. در این قسمت الگوریتم تصادفی برای این کار ارائه می شود. :)

2- الگوریتم تصادفی افزایشی seidel برای دو بعد

نیم صفحه = خطی که یک طرف آن مورد نظر است! :))

جواب محدب است: چون تقاطع(اشتراک) یک سری نیم صفحه است.

اگر جواب در این نیم صفحه باشد، تغییری نده، در غیر این صورت تقاطع CH جواب مرحله قبل را با این نیم صفحه جدید پیدا کن و جواب جدید روی این شکل جدید است. (مثل این که با یک خط چند ضلعی محدب جواب قسمت قبل را ببریم!). برای پیدا کردن جواب جدید باید در یک بعد مساله را حل کنیم (چون خطی که جواب روی آن است را داریم: همین خطی که جدید اضافه کردیم.)

* فکر کنم زمان O(n) برای حساب کردن تقاطع لازم است وگرنه می دانیم خط حداکثر در دو جا CH را قطع می کند و مینیمم گرفتن بین این دو نقطه O(1) می شود.

زمان الگوریتم:

T(n) = T(n-1)+2/n*O(n) = O(n)

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

تعمیم:

برای d بعد زمان d فاکتوریل ضربدر زمان فعلی O(n) می شود. چون هر بار به جای اینکه احتمال ما 2 بر n باشد، d بر n است.

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

3- الگوریتم نمونه گیری تصادفی برای LP ارائه شده توسط clarkson

ایده: نیم صفحه های اضافی را دور بریز

(در واقع تصادفی شده ی همان الگوریتمی است که در قسمت قبل دیدیم.)

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

فضای نمونه: کل شرطها

احتمال انتخاب جواب بدون نمونه گیری (مثل قسمت قبل کمتر از 2 تقسیم بر n است.)

نمونه گیری: مجموعه نیم صفحه های شامل جواب و راس CH نهایی که در این مجموعه می افتد.

احتمال اینکه راس جواب که یکی از راسهای CH نهایی است انتخاب شود کمتر از انتخاب شدن همه ی راسهای جواب بهینه است.

با نمونه گیری انجام شده، احتمال اینکه از بین قیدهای انتخاب شده (d*sqrt(n) تا قید) یک راس از CH نهایی باشد، sqrt(n)*lgn است.

اگر فرض کنیم جواب را برای cd2 قید می توانیم در زمان خوبی به صورت قطعی به دست بیاوریم، (حالت پایه الگوریتم) داریم:

تعداد اعضای هر نمونه حداقل c*sqrt(n)*lgn باید باشد که احتمال رسیدن الگوریتم به جواب n^-cd شود. (چون راه حل تصادفی است، بین زمان الگوریتم و احتمال رسیدن آن به جواب چنین رابطه ای وجود دارد.)

الگوریتم از نوع las vegas است و احتمال موفقیت (برنولی) در آن c*sqrt(n)*lgn است که وقتی d+1 مرحله انجام می شود به مقدار بالا برای موفقیت می رسیم.

زمان اجرا:

T(n)=(d+1)*T(cd*sqrt(n)logn)+O(d2*n) = O(d*d*n+d^d)

که زمان d^d مربوط به همان حالت پایه است که قطعی آن را به دست می آوریم.

بهترین زمان الگوریتم های تصادفی: O(d*d*n+2^sqrt(dlog)) است.

الگوریتم های LP

در قسمت قبل دیدیم که یک سری قید خطی (خط) داریم و می خواهیم در یک جهت اکسترمم (اینجا فرض کنید فقط مینیمم) را به دست بیاوریم.

0- الگوریتم بدیهی

برای شرط هایی که بالای یک خط را نشان می دهند upper envelop را حساب کنیم برای آن شرطهایی که زیر خط بودن رو نشان می دهند lower envelop بعد بین این دو اشتراک بگیریم.

زمان: O(nlogn)

1- الگوریتم هرس و جستجو (prune & search) در دو بعد

(*خودم حدس می زنم برای اینکه جواب O(n) بوده و زمان الگوریتم O(nlogn) سعی کردند که طوری بسازند که فقط حالت های مطلوب ساخته بشه)

فرض کنید می خواهیم x را مینیمم کنیم. (با تغییر متغیر می شود به این حالت رسید.)

ایده: اگر یک خط عمودی رسم کنیم و جواب در یک سمت آن باشد، سمت دیگر آن هرس می شود.

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

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

همین کار را تکرار می کنیم تا جواب به دست بیاید.

زمان: T(n) = T(3n/4)+O(n)=O(n)

چون هر بار از نیمه ی سمت راست (یا چپ) نصف خطوط حذف می شوند.

تعمیم: برای ابعاد بالاتر هم همین کار را می توان انجام داد و زمان آن در دو به توان دو به توان d ضرب می شود. بهبود یافته ی آن در دو به توان d2 کار می کند. بهترین الگوریتم در n در دو به توان dlogd کار می کند. (d = تعداد ابعاد)

کاربردهای LP

برنامه ریزی خطی (Linear Programming): تعدادی قید خطی (نامساوی) داریم و می خواهیم یک تابع خطی از همین متغیرها را مینیمم کنیم. بهترین زمان آن O(n) است.

1-خط تقسیم کننده:

دو مجموعه نقطه با n عضو داده شده است. خطی که آنها را تقسیم می کند پیدا کنید.

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

متغیرها: شیب خط و عرض از مبدا خط (جدا کننده)

تابع هدف: مثلا مینیمم m: چون تعداد خطهای جواب زیاد است، مهم نیست کدام را بدهد، مثلا می گوییم خط با شیب کمتر را بده.

2-برازش خط:

مجموعه n نقطه داده شده است، می خواهیم خطی را پیدا کنیم که فاصله ی عمودی (y) آن با نقاط مینیمم شود.

قید: فاصله عمودی نقاط تا خط (معادله ی خط در x آن نقطه را می نویسیم و منهای y نقطه می کنیم و قدر مطلق می گیریم). این باید بین d و 0 باشد. (برای اینکه خطی شود هر قید را به دو قید تبدیل می کنیم که قدر مطلق را برداریم.)

متغیر: شیب خط و عرض از مبدا خط و d (حداکثر فاصله عمودی یک نقطه تا خط)

تابع هدف: مینیمم کردن d

3- دو دایره هم مرکز پیدا کنید که همی نقاط بین این دو دایره بیفتند و مساحت بین دو دایره مینیمم شود.

تابع هدف: مینیمم کردن مساحت بین دو دایره (مساحت بزرگتر منهای کوچکتر: درجه یک نسبت به توان دو شعاع)

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

متغیرها: R2-x2-y2 و r2-x2-y2 و x و y (مرکز دایره)

4- کوچکترین دایره محیطی

مجموعه n نقطه داده شده است. دایره با کوچکترین شعاع را بیابید که همه ی نقاط را شامل شود.

قید: فاصله هر نقطه تا مرکز دایره (درجه 2)

متغیرها: مرکز دایره و شعاع دایره

تابع هدف: مینیمم کردن شعاع دایره

*خطی نیست اما محدب سه بعدی است.