هندسه ترکیبیاتی

*مسأله‌ی سیلوستر: تعدادی نقطه در صفحه داریم می‌شود همیشه خطی پیدا کرد که دقیقاً از ۲ تا نقطه بگذرد؟ (فرض کنید همه روی یک خط نیستند)

بله، اثبات: برهان خلف:

به ازای هر سه نقطه غیر هم خط فاصله‌ی یکی را از دو نقطه‌ی دیگر در نظر می‌گیریم و مینیمم این مجموعه را نقطه r و پاره‌خط pq می‌نامیم. نقطه‌ی دیگری که روی خط گذرنده از p و q است را s می‌نامیم. (چون می‌دانیم هر خطی طبق فرض خلف از دقیقاً دو نقطه نمی‌گذرد و اینجا p و q روی خط هستند پس از حداقل ۳ نقطه می‌گذرد.)

اگر پای عمود رسم شده از r روی pq بیفتد طبق نامساوی مثلث فاصله‌ی رأس نزدیک‌تر به s از rs کمتر از فاصله‌ی مینیمم است که این تناقض است.

اگر پای عمود رسم شده از r بیرون pq بیفتد طبق نامساوی مثلث فاصله‌ی رأس نزدیک‌تر به s از خط گذرنده از r و نقطه‌ی دورتر به s کمتر از فاصله‌ی مینیمم است که تناقض است.

*مسأله‌ی هاپکرافت: n نقطه و n خط داریم، حداکثر تعداد incidence ها چندتا است؟ (یعنی نقطه روی خط بیفتد و اگر یک نقطه روی تقاطع چند خط باشد چند بار شمرده می‌شود.)

کران ساده: خطوط را به m دسته‌ی n/m تایی تقسیم کنیم و در هر کدام می‌دانیم تعداد تقاطع‌ها حداکثر تعداد خط‌ها به توان ۲ است. از اینجا m طوری به دست می‌آید که O(n^3/2) وقوع (incidence) داریم. از روی جمع درجات=تعداد یالها*۲ می‌فهمیم چون هر وقوع معادل عبور یک خط از یک نقطه است که درجه آن نقطه را ۲ تا زیاد می‌کند.

کران بهتر:

O(n+x) که x تعداد تقاطع‌ها است. طبق crossing lemma (لم تقاطع)‌ تعداد یالهای O(n+n^2/3 x^1/3) است. با جایگذاری O(n^4/3) به دست می‌آید.

*مسأله‌ی اردوش: n نقطه داریم چند تا فاصله‌شان از هم دقیقاً ۱ است؟

دور هر نقطه دایره به شعاع ۱ می‌زنیم. همان اثبات مسأله‌ی هاپکرافت را می‌توانیم برای این مسأله به کار ببریم چون از خط بودن هیچ استفاده‌ای نکرده‌ایم.

هندسه پیشرفته (مرور جلسه دوم)

الگوریتم‌های جلسه قبل از مرتبه O(dn) بودند یعنی برای ابعاد بالا قابل استفاده نیستند. پس یک بار دیگر عملکرد الگوریتم‌های جلسه قبل را بررسی می‌کنیم.

فرض کنید همان طور که با پیدا کردن دورترین نقطه از نقطه فعلی الگوریتم دوم را از روی الگوریتم اول به دست ‌آوردیم کار را ادامه می‌دادیم. اگر نقاط بیشتری را درگیر حل مسأله کنیم و دورترین نقطه از آنها را پیدا کنیم مجموعه‌ای از جواب‌ها را داریم که هر کدام در یک جهت نقاط را در بر‌می‌گیرند (جواب مسأله هستند). پس اگر تعداد جهت‌های مناسب با فاصله‌ی مناسب انتخاب کنیم می‌توانیم جواب مسأله را با تقریب خوبی به دست بیاوریم. یک راه این کار در نظر گرفتن نقاط با فاصله یکسان روی سطح کره است و دیگری در نظر گرفتن جهت با وصل کردن مرکز مکعب به وسط هر خانه توری. چون سطح مطرح شده است از مرتبه‌ی d-1 یک بر اپسیلون است.

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

ما عمل مقیاس کردن را در روش توری انجام دادیم و روش تصویر کردن جهتی را هم الآن بررسی کردیم. می‌توانیم این دو را ترکیب کنیم چون خروجی الگوریتم توری یک مجموعه نقاط است و می‌توان مجدداً روی آنها الگوریتم دیگری اجرا کرد. با این کار تقریب مورد نظر به هم نمی‌خورد چون نقاط درون یک خانه‌ی توری از نظر زاویه به هم نزدیک هستند. در غیر این صورت باید ضریب تقریب‌ها را جمع می‌کردیم و ضریب تقریب دو برابر می‌شد.

چون تقریب در واقع به توری وابسته است، به جای اینکه ابتدا نقاط سطح توری را به دست بیاوریم بعد آنها را رند کنیم می‌توانیم از روی توری جواب مسأله را هم تقریب بزنیم. یعنی دورترین نقطه را از هر نقطه توری در هر ابرصفحه حساب کنیم. این کار باعث می‌شود نقاطی که می‌دانیم جزو جواب نیستند را در نظر نگیریم. برای این کار به صورت افزایشی تعداد ابعاد را زیاد می‌کنیم و هر بار نقاطی را که نسبت به نقاط قبلی دورترین هستند نگه می‌داریم. در خود مقاله گفته است که نقاط دیاگرام ورونوی گسسته دوگان دورترین نقاط در جهت‌های داده شده هستند.

من الآن دارم مقاله را می‌خوانم و حس می‌کنم این‌ها هیچ ربطی به مطالب مقاله ندارند.

هندسه پیشرفته با رویکرد مهندسی معکوس (مرور جلسه اول)

از آنجایی که من خودم وقتی درس می‌خوانم فقط مدل‌ها را یاد می‌گیرم نه روش‌ها را تصمیم گرفتم که بنویسم به نظر من ایده‌ی این روش از کجا به ذهن اولین نفری که آن را ارائه داده، رسیده است.

روش اول که پیدا کردن دورترین نقطه است از اینجا به ذهن می‌رسد که ماکسیمم فاصله هر دو نقطه قطر را می‌دهد. برای اثبات تقریب باید به ازای هر نقطه p از نقاط اولیه ثابت کنیم که دو نقطه‌ی جواب (مثلا a و b) تقریبی از قطر می‌دهند.

ALG < OPT < c*ALG

max(pa,pb) < ab < pa+pb < 2*max(pa,pb)

یعنی اگر ماکسیمم فاصله‌ از هر نقطه دلخواهی را به عنوان جواب برگردانیم ۲-تقریب جواب بهینه است.

این معادل زدن یک دایره به مرکز p و شعاع دورترین نقطه از آن است. می‌دانیم دورترین نقطه روی محیط می‌افتد (چون فاصله‌اش تا مرکز برابر شعاع دایره است). دورترین نقطه از این نقطه را هم پیدا می‌کنیم و به مرکز آن و شعاع این نقطه جدید (مثلا q) دایره می‌زنیم. همه‌ی نقاط درون اشتراک این دو دایره می‌افتند. در یک حالت نقطه‌ی q روی دایره‌ی اول می‌افتد (بدترین حالت در روش قبلی) و وقتی ما ماکسیمم این دو جواب را برمی‌گردانیم به جواب بهینه می‌رسیم چون حداکثر فاصله‌ی دو نقطه از قطر دایره کمتر است. یعنی بدترین حالت روش قبلی تبدیل به بهترین حالت روش جدید شده است. اما بدترین حالت روش فعلی چیست؟ اینکه فاصله‌ها برابر باشند. در این صورت دایره دوم از مرکز دایره‌ی اول عبور می‌کند و مرکز خودش هم روی محیط دایره اول است. (پس دو دایره مساوی داریم.) حداکثر فاصله‌ی دو نقطه در این حالت عمود منصف بین‌المرکزین است که رادیکال ۳ برابر بین‌المرکزین است.

می‌خواهیم دقت بیشتری داشته باشیم. برای حل این مشکل از مقیاس دادن استفاده می‌کنیم، یعنی مثلا دورتر می‌ایستیم و نقاط نزدیک به هم را یکی می‌بینیم. این کار را با استفاده از توری انجام می‌دهیم. بعد از اینکه جواب را در مقیاس بالاتر به دست آوردیم نزدیک‌تر می‌شویم و جواب را بهتر می‌کنیم. (مثل عمل zoom). برای این کار از یک تقریب قبلی (مثل دو الگوریتمی که گفته شد) استفاده می‌کنیم بعد یک توری با کمک کوچکترین جعبه محیطی می‌سازیم که اندازه‌ی خانه‌های آن اپسیلون برابر تقریب قطر است و نقاط را به نزدیک‌ترین گوشه توری رند می‌کنیم. حالا طبق تقریبی که از قطر به دست آورده‌ایم می‌دانیم تعداد خانه‌های توری که واقعاً به کار می‌روند در هر بعد از یک بر اپسیلون کمتر است پس کلاً تعداد نقاط جدید ما یک بر اپسیلون به توان d خواهد بود. (d تعداد ابعاد است.)

حالا الگوریتم brute force را روی این نقاط جدید که تعداد کمی دارند (همان طور که گفته شد وابسته به اپسیلون است.) اجرا می‌کنیم که مرتبه‌ی n^2 است و زمان ما همچنان خطی بر حسب n و یک بر اپسیلون خواهد بود. (PTAS) زمان خطی مربوط به رند کردن نقاط به توری است که با یک کف گرفتن (جزء صحیح) انجام می‌شود.

ضریب تقریب آن رادیکال d برابر عرض هر خانه (=قطر هر خانه) خواهد بود که چون تعداد ابعاد را از قبل می‌دانیم می‌توانیم به هر اپسیلون دلخواهی برسیم.

در این توری می‌دانیم که نقاطی که درون مکعب می‌افتند تاثیری در محاسبه‌ی قطر ندارند پس با در نظر گرفتن نقاط روی سطح آن می‌توانیم توان یک بر اپسیلون را در محاسبه‌ی تعداد نقاط یکی کم کنیم.

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

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

ساختمان داده‌ای بسازید روی مجموعه نقاط 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 نقطه همسایه باید برای آن نگه داریم.

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

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

مجموعه P از n نقطه در فضای d بعدی داده شده است، توپی که شامل همه ی نقاط P شود و کمترین شعاع (r*) را داشته باشد پیدا کنید.

کاربردها: facility location، حجم محیطی

*الگوریتم های دقیق

- برنامه نویسی محدب (convex programming) (به این مسائل LP-Type می گویند: شبیه برنامه ریزی خطی حل می شوند.)

زمان O(n) برای d ثابت

ابعاد بالا؟

روشهای هندسی:

O(d^2 n+ 2^O(sqrt(d lg d)) ) تصادفی

O(2^O(2^d) n) قطعی

روشهای غیر هندسی:

O( polynomial(n,d,#bits)) با روش Ellipsoid و ...

* الگوریتم تقریبی

ایده: هسته

زیرمجموعه S از P را پیدا کنید که 

(1-epsilon)*min_rad(P)<= min_rad(S) <= min_rad(P)

*الگوریتم ساده با ضریب تقریب 2

s: هر نقطه ی دلخواه

t: دورترین نقطه از s

جواب: {s,t}

تحلیل:

فرض کنید r جواب الگوریتم باشد. در بهترین حالت دو نقطه دو سر قطر هستند و جواب بهینه به دست می آید. در حالت کلی می دانیم t دورترین نقطه از s است پس بقیه نقاط همه در دایره به مرکز s و شعاع st می افتند.

r >= min_rad({s,t})=||s-t||/2 >= r*/2

مزیت این الگوریتم این است که با یکبار دیدن داده ها می تواند جواب را به دست بیاورد. پس برای مدل streaming هم جواب می دهد.

*الگوریتم جویبار داده (Z, Chan, 2006)

ایده: حرکت دادن مرکزها

1) B=empty set

2) for i = 1, 2, ...

3)     B=min ball enclosing B and Pi

تحلیل:

فرض کنید Pi روی محیط دایره ی بهینه (B*) باشد. (این بدترین حالتی است که می تواند رخ بدهد.) دایره ای که Pi روی محیط آن است Bi می نامیم که مرکز ci و شعاع ri دارد. ti را هم فاصله ci (مرکز دایره iام) تا محیط دایره بهینه می گیریم، در امتداد خط گذرنده از Pi. (فاصله بین Pi و ci که ri است نه سمت دیگر!)

ادعا: ri <= 3*ti

اثبات: استقرا روی نقاط

از قضیه هندسه دبیرستان که حاصلضرب قسمت های دو وتر متقاطع با هم برابرند استفاده می کنیم. (در دایره بهینه)

دلتا = فاصله ی بین مرکز دایره ci و c(i-1)

delta = ||c_i-c_(i-1)||

(intersection point: c_(i-1) ):  r_(i-1)*t_(i-1) = (r_i+delta)*(ti-delta)

گام استقرا:

3*ti = 3*( r_(i-1)*t_(i-1)/(r_i+delta) +delta)

طبق فرض استقرا

3*t_(i-1) >= r_(i-1)

==>

3*ti >= 3*( r_(i-1)*[1/3*r_(i-1)]/(r_i+delta) + delta ) = ... = r_i+4*delta^2 / (r_i+delta) >= r_i

پایان اثبات ادعا

اثبات ضریب تقریب:

دایره ی B* را در نظر بگیرید. داریم:

ri+ti <= 2 r*

(lemma) ==> 4/3 ri <= 2 r* ==> r_i <= 3/2 r*

factor = 3/2

O(d) space

؟؟ چرا فضای لازم O(d) است؟

این بهبود داده شده است.

*الگوریتم تکرار شونده

1) یک نقطه q0 از P را بردار.

2) به ازای i از 1 تا ...

3) کوچکترین توپ که شامل نقاط 0 تا i-1 می شود را محاسبه کن. (مرکز ci)

4) qi را دورترین نقطه از ci بگیر.

تحلیل:

r* / 2 <= r2 <= r3 <= ... <= r*

{چون دو نقطه ی اول که بر می داریم ممکن است در آخر مرکز دایره و یک نقطه روی محیط دایره باشند.}

حقیقت 1) هر نیم کره کوچکترین دایره ی محیطی یک مجموعه نقاط دارای حداقل یک نقطه از بین نقاط هست.

چون در غیر این صورت می توانیم دایره را به سمت دیگر حرکت بدهیم و کوچکتر کنیم تا دو نقطه سر قطر یا سه نقطه روی آن بیفتند که با کوچکترین دایره محیطی بودن متناقض است.

حقیقت 2) اگر نقطه ی جدید خارج توپ بیفتد، حتما در توپ جدید این نقطه روی محیط است.

اثبات: برهان خلف. دایره ی بهینه که شامل نقطه جدید و نقاط قبلی است در نظر بگیرید که نقطه ی جدید هم درون دایره افتاده است. نقاط قبلی در اشتراک دایره جدید و دایره قدیم اند. پس دایره ی شامل اشتراک این دو دایره و نقطه ی جدید که شعاع کمتری دارد شامل همه ی نقاط تا کنون می شود که تناقض است با مینیمم بودن دایره جدید.

نتیجه) روی دایره Bi یکی از نقاط قبلی هست که زاویه بین مرکز دایره مرحله بعد و این نقطه و مرکز دایره فعلی کمتر از 90 درجه است.

اثبات:

{ نمی دانم چرا در خود مقاله به ازای همان j گفته بود اما اینجا به ازای مرکز دایره ی بعدی و این دایره گفته است. الآن جا دارد مثل روزنامه ها بزنم عکس تزئینی است! :)) }

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

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

جلسه ششم

الگوریتم 2: برای عرض در 2 بعد با تقریب ثابت (chan 2004)

ایده: تکنیک دوبرابر کردن

مقدار دهی اولیه: s: نقطه ی اول؛ t: نقطه دوم؛ width=0

اضافه کردن نقطه p:

w = max( w, width(triangle(s,t,p)) )

if ||s-p|| > 2.||s-t|| then t = p

این روش در واقع اصلاح شده ی همان روش پیدا کردن دورترین نقطه از st است ولی چون آن الگوریتم 2 بار داده ها را می دید برای مدل جویبار داده مناسب نبود.

شرطی که در خط دوم الگوریتم است برای اصلاح st مورد استفاده در مرحله بعد است و جواب این مرحله همان w است که در خط اول به دست می آید.

تحلیل:

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

dist(p, line(s,ti)) <= 3w

اثبات:

area of triangle(s,p,ti) = dist(p, line(s,ti) ) * ||s-ti|| = dist(s, line(p,ti)) * ||p-ti|| (1)

line 1 alg'm ==> dist(s, line(p,ti)) <= w (2)

(1),(2) ==> dist(p, line(s,ti) ) * ||s-ti|| <= w*||p-ti|| (6)

triangle inequality ==> ||p-ti|| <= ||p-s||+||s-ti|| (3)

line 2 alg'm ==> ||s-p|| <= 2*||s-ti|| (4)

(3),(4)==> ||p-ti|| <= 3*||s-ti|| (5)

(6),(5) ==> dist(s,line(p,ti)) *||s-ti|| <= w*3*||s-ti||

==> dist(s,line(p,ti)) <= 3*w

(

* اثبات عرض مثلث

تقریب هسته ای که قبلا حساب کرده بودیم، سه حالت دارد که هر بار نسبت دو ضلع را بررسی می کنیم و در بین همه ی این حالت ها نسبت عرض محاسبه شده و جواب حداکثر 3 برابر است.

)

محاسبه تقریب بعد از به روز رسانی

dist(p, line(s,t(i+1)) ) <= dist(p, line(s,ti) ) + dist( p^, line(s,t(i+1)) )

چون خط عمود از p^ (که تصویر p روی line(s,ti) است)  به line(s,t(i+1)) با خط عمود از ti به این خط موازی است، طبق تالس داریم:

<= dist(p,line(s,ti))+||s-p^||/||s-ti|| * dist(ti, line(s,t(i+1))

line 1 alg'm ==>

<= dist( p,line(s,ti) ) + ||s-p^||/||s-ti|| *3*w_opt_i

فاصله ی عمودی از هر فاصله ی دیگری کمتر است

<= dist( p, line(s,ti) ) + ||s-p||/||s-ti|| *3w_opt_i (1)

line 2 alg'm ==> ||s-p|| > 2*||s-ti|| ==> ||s-t(i+1)|| > 2*||s-ti|| (2)

(1),(2) ==> dist(p, line(s,t(i+1)) ) <= dist(p, line(s,ti)) + 2*3*w_opt_i

==> w_alg_(i+1) <= w_alg_i+6*w_opt_i

==> w_alg_(i+1)  <= w_alg_0 + 2*3*w_opt_1+...+2*3*w_opt_i

proof of part 1 (w_alg_0 <= 3w_opt) ==> w_alg <= 3w_opt+2*3*w_opt_1+...+2*3*w_opt

line 2 alg'm (update) ==> 2*w_opt_i <= w_opt_(i+1)

==> w_alg <= 3w_opt+(..+1/4+1/2+1+2)*3w_opt <= 15w_opt

مقدار درست آن 18 است که با تحلیل بهتر به دست می آید اما تا همینجا به تقریب 30 می رسیم. (؟؟)

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

الگوریتم 3: تقریب عرض نقاط در مدل جویبار با استفاده از هسته ی گستره نقاط در دو بعد

ایده: تکنیک دو برابر کردن

s=نقطه اول، t=نقطه دوم

اضافه کردن نقطه p:

0- خطوط توری عمود بر st را با فاصله ی epsilon*||s-t|| رسم کن.

1- نقطه p را به نزدیک ترین خط توری رند کن.

2- تنها نقاط مینیمم و ماکسیمم را روی هر خط نگه دار.

3- اگر ||s-p|| >= 2||s-t است آنگاه t=p و خطوط توری را دوباره رسم کن و نقاط فعلی را دوباره رند کن.

تحلیل:

فضای حافظه : O(1/epsilon)

ضریب تقریب:

هر قدم رند کردن a.p را به اندازه epsilon*w_s{s,ti} <= epsilon*w_a(P_ تغییر می دهد.

بعد از log(1/eplsilon) گام رند کردن،

||s-p|| < epsilon* ||s-ti||

پس p روی خط توری گذرنده از s می افتد. (اولین خط توری)

هر قدم رند کردن a.p را به مقدار زیر تغییر می دهد:

<= L / ||s-ti|| * w_a(s,ti) <= ||s-p||/||s-ti|| w_a(P)

که L فاصله ی بین خط توری گذرنده از s و خط گذرنده از sp است.

{فکر کنم خط توری مرحله جدید و قبلی}

total error <= O(epsilon lg 1/epsilon)*w_a(P)+w_a(P)*epsilon*(1+1/2+...) <= O(epsilon lg 1/epsilon) w_a(P)

space: O(1/epsilon lg 1/epsilon)

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

جلسه پنجم

مدل جویبار داده (Streaming Model)

تعریف: یک الگوریتم stream الگوریتمی است که ورودی را در یک عبور (pass) می بیند و حافظه محدود دارد. {بهتر است بگوییم جویبار داده نامحدود است!}

*حل مساله قطر با جویبار داده

الگوریتم دقیق:

برای یک بعد: با محاسبه مینیمم و ماکسیمم با O(1) حافظه به دست می آید و با یک pass انجام پذیر است.

برای دو بعد: حداقل به اندازه ی تعداد نقاط حافظه نیاز داریم چون ممکن است نقطه ای که آن را حذف می کنیم (هر نقطه ای!) در آینده یکی از دو نقظه ی مرزی در محاسبه قطر نقاط باشد.

پس برای بیشتر از یک بعد نمی توانیم الگوریتم جویبار داده ی دقیق بدهیم.

الگوریتم تقریبی:

روش 0 (پیدا کردن دورترین نقطه از یک نقطه): O(1) حافظه می خواهد و در یک عبور امکان پذیر است.

روش 1 (پیدا کردن دورترین نقطه از یک نقطه و دورترین نقطه از آن): به دو عبور نیاز دارد. (نمی شود)

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

روش 3 (رند کردن نقاط در جهت های مختلف): می شود چون بیشتر از یک عبور نیاز نداریم. حافظه ی O(1/epsilon^((d-1)/2)) می خواهد.

* مزیت الگوریتم 0 این است که در ابعاد بالا هم کار می کند، اما الگوریتم 3 نمایی است.

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

*آیا می توان مساله نزدیک ترین دو نقطه را در مدل جویبار داده حل کرد؟ خیر، حتی نمی توان تقریب زد.

*آیا می توان مساله عرض نقاط را با این حل کرد؟ بله، با همان coreset گستره نقاط (extent)

*محاسبه عرض نقاط

الگوریتم 1: یک epsilon-هسته از نوع گستره نقاط پیدا کن

ایده: ادغام و کاهش (به آن روش لگاریتمی هم می گویند.)

اضافه کردن نقطه:

1) یک هسته شامل مجموعه تک عضوی {p} بساز. (سطح 0)

2) تا وقتی 2 هسته ی S1 و S2 به ترتیب برای مجموعه نقاط P1 و P2 وجود دارند و در یک سطح هستند:

2-1) اپسیلون هسته ی S که اجتماع S1 و S2 است محاسبه کن.

2-2) S را به عنوان هسته ی P1 U P2 در سطح i برچسب بزن. {حس می کنم اینجا باید i+1 باشه!}

2-3) S1 و S2 را حذف کن.

{جواب هم باید هسته ای باشه که در مرحله ی آخر =بالاترین سطح درخت باقی می ماند.}

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

{البته فکر کنم کاهش منظور همان ساختن هسته و کاهش نقاط است.}

تحلیل

تعداد سطح ها: O(log n)

فضای لازم: O(1/epsilon^d lg n) (اصطلاحاً polylog( n))

زمان: O(1/epsilon^d n)

( ضریب 1/epsilon^d از اندازه ی هسته می آید. lg n از عمق درخت. n از تعداد ادغام ها= کل گره های درخت)

دلیل حفظ ضریب تقریب هسته (هنگامی که دو هسته ادغام می شود) این است که هسته های قبلی نقاط مجزا داشته اند:

*اگر S1 یک اپسیلون-هسته برای P1 و S2 یک اپسیلون-هسته برای P2 باشد، S1 U S2 یک اپسیلون-هسته برای P1 U P2 است.

*اگر S یک اپسیلون-هسته برای Q باشد و Q یک اپسیلون پریم-هسته برای P باشد، آنگاه S یک (اپسیلون+اپسیلون پریم) - هسته برای P است.

(چون ضریب تقریب های آنها جمع می شود.)

در کل یک O(epsilon* log n)-هسته به دست می آید. اپسیلون را طوری تعیین می کنیم که log n حذف شود:

epsilon' = epsilon/lg n

و با این اپسیلون جدید هسته ها را به دست می آوریم.

فضای کل لازم O( 1/epsilon^(d-1) log^d n) است.

این مدل برای جویبار داده قابل استفاده هست اما می خواهیم مستقل از n کنیم.

جلسه چهارم

هسته های هندسی

*هسته ی گستره ی نقاط (extent)

الگوریتم دقیق: O(n^c) که c ثابت است. {سه نقطه داشته باشیم به دست میاد پس n^3 تا برای ساختن دو خط موازی n تا برای چک کردن اینکه همه نقاط بین انها هستند پس c از 4 کمتر است.}

الگوریتم تقریبی: (با استفاده از هسته گستره نقاط)

محاسبه ی هسته O(n) {پیدا کردن دور ترین نقطه از یک نقطه و دورترین نقطه از یک خط}

محاسبه ی جواب دقیق مساله برای هسته: ( O( ((1/epsilon)^c')^c {اینجا c' احتمالا همان d یا d-1 و مثل آن است و یک بر اپسیلون هم تعداد نقاط هر بعد است پس کلا همان اندازه ی هسته به دست می آید.}

زمان کل: O(n+(1/epsilon)^c'c)

* تعمیم به ابعاد بالاتر (هسته ی گستره نقاط)

فرض کنید مبدا جزو نقاط باشد.

1) به ازای ابعاد از 1 تا d بعد:

2) دورترین نقطه را به ابرصفحه ی (j-1) بعدی ( j-1)-flat) ) گذرنده از مبدا و نقاط قبلی پیدا کنید.

3) عرض مجموعه نقاط به دست آمده در مرحله 2 الگوریتم را به دست آورید.

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

d*O(nd) = O(nd^2) ==> O(n)

ضریب تقریب الگوریتم:

تصویر بردار متناظر نقاط قبل روی ابرصفحه های (j-1) بعدی تشکیل یک پایه (نه لزوما متعامد) می دهد. می دانیم هر کدام از نقاط را می توان به صورت ترکیب خطی از بردارهای این پایه نوشت که ضرایب آنها قدر مطلقشان از 1 کمتر مساوی است (چون دورترین نقطه را هر بار انتخاب کرده ایم.)

قضیه: اگر بردار پایه بعد j-ام u_j باشد و مجموعه نقاط مرحله 2 (شامل مبدا مختصات) را S بنامیم و a هر بردار جهت دلخواه باشد، داریم:

|a.u_j| <= 2^(j-1) * width_a (S)

اثبات: استقرا روی تعداد ابعاد

پایه استقرا: یک بعد

a.u_1=a.v_1 <= width_a (S)

فرض استقرا: برای بعدهای 1 تا j-1 درست است.

حکم استقرا: برای بعد j ام:

u_j = v_j+sum_k_1_(j-1) (b_k*u_k) , |b_k| <= 1

(یعنی اگر از بردار v_j تصویر آن را در راستای بردارهای ابعاد قبل کم کنیم، تصویر آن روی ابرصفحه ی بردارهای قبلی به دست می آید.)

|a.u_j| <= |a.v_j|+sum_k_1_(j-1) (|a.u_k|)

(بردار a را در تساوی قبلی ضرب کرده ایم و از b_k <=1 استفاده کرده ایم.)

<= width_a (S)+sum_k_1_(j-1) (2^(k-1)*width_a(S) ) = 2^(j-1)*width_a(S)

(چون بردار a یکه است، ضرب داخلی آن در هر برداری تصویر آن بردار را در جهت a می دهد. که عرض نقاط از تصویر بردار در آن راستا بیشتر است.

از جلسه قبل داشتیم که دو برابر عرض نقاط از تصویر هر برداری در هر راستایی بیشتر است و تصویر بردار از عرض نقاط بیشتر است؛ که این دلیل نامساوی دومی است.)

نتیجه: به ازای هر نقطه p از مجموعه نقاط ورودی داریم:

|a.p| <= sum_j_1_d (|a.u_j|) <= sum_i_1_d ( 2^(j-1)*width_a(S) ) <= 2^d*width_a(S)

از اینجا ضریب تقریب الگوریتم را به دست می آوریم: (p و q دو نقطه از نقاط ورودی هستند)

|a.(p-q)| = |a.p-a.q| <= |a.p|+|a.q| <= 2* 2^(d) * width_a(S) =2^(d+1) * width_a(S)

==> width_a(S) <= width_a(P) <= 2^(d+1) * width_a(S)

factor = 2^(d+1)

*بهبود: 

قضیه: می توانیم تبدیل آفینی پیدا کنیم که به ازای هر بردار جهت، عرض نقاط بین دو مقدار ثابت باشد.

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

اثبات:

نقاط را در جهت بردارهای پایه (u_i) تجانس ( کلی فکر کردم یادم اومد چند برابر کردن اسمش چیه! :)) ) بدهیم طوری که اندازه ی آنها 1 بشه. (به ترتیب از بعد 1 تا d)

بعد از تبدیل:

c/2^(d+1) <= width_a(P) <= 2*sqrt(d)

چون همه ی نقاط بعدهایی بین 1 و -1 دارند، یعنی در ابرمکعب dبعدی قرار می گیرند، حداکثر فاصله شان 2 رادیکال d است. (نامساوی سمت راست)

نامساوی سمت چپ ؟؟

* هسته مجموعه نقاط P

1) تبدیل را روی P انجام بده.

2) یک توری به طول اپسیلون روی آن بساز.

3) به ازای هر خانه توری، یک نقطه از آن را در S نگه دار.

تحلیل:

به ازای هر بردار جهت a داریم:

|width_a(S) - width_a(P)| = O(epsilon) = O(epsilon*width_a(P))

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

width_a(S) / width_a(P) = 1-O(epsilon)

==> O(epsilon)-coreset

اندازه هسته:

#grid cells = O(1/epsilon^d)

*مساله عرض نقاط:

O(n+(1/epsilon^d)^ceil(d/2) ) {using exact algorithm}

O(n+1/epsilon^((d-1)/2)*1/epsilon^((d-1)/2) ) = O(n+1/epsilon^(3/2(d-1)) ) {using algorithm 1: dir. rounding+skewed width}

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

نکته: بعد از تبدیل گرفتن جهت ها را رند کنیم.

نکته: می توانیم از نوعی دیاگرام ورونوی گسسته استفاده کنیم. {نزدیک ترین نقطه به جای دورترین نقطه که در قطر استفاده کردیم.} که این کار زمان زیر را می دهد:

O(n+1/epsilon^(d-1))

نکته: بهترین اندازه هسته ممکن:

O(1/epsilon^((d-1)/2) ) {by Agrawal}

نکته: هسته گستره نقاط برای پوسته محدب کار می کند.

نکته: هسته گستره نقاط برای مسائل دیگری مثل پیدا کردن دو دایره هم مرکز با کمترین فاصله که همه ی نقاط را بپوشانند؛ هم کار می کند.

جلسه سوم

عرض نقاط

مجموعه P از n نقطه در فضای d بعدی داده شده است، کمترین فاصله بین دو ابرصفحه موازی را پیدا کنید که همه ی نقاط بین دو ابر صفحه بیفتند.

= پیدا کردن ابرصفحه ای که فاصله ی دورترین نقطه از آن مینیمم شود. (صفحه ی بین دو ابرصفحه ی موازی قبل این صفحه است.)

الگوریتم های دقیق:

2بعد: anti-podal pair و پوسته محدب O(nlogn)

3بعد: تصادفی Agrawal,Sharir 1995 زمان ((O(n^(3/2+epsilon

4 بعد و بیشتر: O(n^ceil(d/2))

تعریف ریاضی مساله:

w* = min (1/ sqrt(n1^2+n2^2+...+nd^2) )

s.t. h <= x1*n1+...+xd*nd <= h+1

(parallel planes: x1*n1+...+xd*nd=h, x1*n1+...+xd*nd=h+1)

(variables: (n1,...,nd,h) )

این یک LP نیست چون تابع آن خطی نیست، اما برنامه نویسی محدب است.

زمان حل: O(n^ceil((d+1)/2))

الگوریتم های تقریبی:

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

1- الگوریتم Duncan, Goodrich, Ramus 1997

ایده: رند کردن نقاط با استفاده از جهت و محاسبه عرض کج؟ (skewed width)

1) مجموعه جهت ها را بساز. O(1/epsilon^(d-1)) جهت برای حفظ حداکثر زاویه بردار دلخواه با این جهات.

2) در هر کدام از جهت های قسمت 1، عرض کج را در آن جهت حساب کن. (عرض کج = عرض نقاط در آن جهت)

نحوه ی محاسبه ی عرض کج: یک LP با d+1 متغیر است که d تای آن مربوط به ابرصفحه ی وسط دو صفحه (به تعریف مساله نگاه کنید) هستند و متغیر دیگر مربوط به حداکثر فاصله یک نقطه از این ابرصفحه است که هدف LP هم مینیمم کردن آن است.

با توجه به اینکه نرمال صفحه بردار a (بردار جهت) است که در مرحله ی اول الگوریتم به دست آمده است، نمی دانم چرا در جزوه d+1 متغیر در نظر گرفته شده، باید همان 1 متغیره باشد!

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

#directions * LP(#points)

O(1/delta^(d-1) * n)

*ضریب تقریب:

width_OPT <= width_ALG <= width_OPT/cos(delta)

factor = 1/cos(delta)

1/(1-x) = 1+x+x^2+... >= 1+x

cos(delta) = 1-2*sin^2(delta/2) = 1-2(delta-delta^3/3+...)^2 <= 1-2*delta^2

x=2*delta^2

1/cos(delta) >= 1+2*delta^2

epsilon = 2*delta^2

factor = 1+epsilon

2- الگوریتم Agarwal, Har-peled, vardarajan 2004

ایده: رند کردن نقاط با توری غیر یکنواخت + دوران یافته + مقیاس شده (scaling)

*مساله کلی تر: برای همه ی جهت ها تقریب را به دست بیاوریم: با کمک یک زیر مجموعه از نقاط:

زیر مجموعه ای از نقاط را پیدا کنید که به ازای هر بردار یکه a داشته باشیم:

width_a (all points) >= width_a (subset) >= width_a(all points) *(1-epsilon)

width_a (points) = max_p,q_points (a.(p-q))

به این یک extent (گستره) از نقاط می گویند و یک اپسیلون-هسته است. (epsilon-coreset)

*پیدا کردن هسته با اندازه ی ثابت

الگوریتم تقریبی برای دو بعد با ضریب ثابت:

s: هر نقطه ی دلخواه از مجموعه نقاط ورودی (P)

t: دورترین همسایه s

u: دورترین نقطه از پاره خط st

عرض نقاط: عرض سه نقطه ی قبل

زمان الگوریتم: O(n) که n تعداد نقاط است.

ضریب تقریب الگوریتم:

چون در طرف دیگر خط st هم می تواند نقطه باشد، جواب الگوریتم را دو برابر عرض نقاط هسته می دهیم.

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

الآن باید تقریب هسته را در بیاوریم و در تقریب الگوریتم (=2، چون جواب حداکثر دو برابر عرض نقاط است: همه یک طرف خط st باشند) ضرب کنیم.

تقریب هسته:

هسته ی فعلی ما دو خط موازی اند که یکی از آنها امتداد st است و دیگری خط موازی آن است که از u می گذرد. چون همه ی نقاط باید در فاصله بین این دو خط باشند، مثلث ust در همه ی این هسته ها وجود دارد. 

||u-t|| <=||s-t||+||s-u|| (triangle inequality) <= 2.||s-t|| (t = farthest point from s)

width_ALG*||s-t|| = width_coreset*||u-t|| <=2.||s-t||.width_coreset

==> width_ALG <= 2.width_coreset

پس تقریب الگوریتم 4 است.

جلسه دوم

ادامه ی الگوریتم های محاسبه قطر نقاط

3- الگوریتم تقریبی agrawal, matousek, suri 1992

ایده: رند کردن جهت ها (به جای اینکه نقاط ورودی را رند کنیم، نقاط خروجی را رند می کنیم.)

1- مجموعه ای از جهت ها به دست بیاور. (هر جهت a)

2- نقاط مرزی p_a و q_a را در جهت a به دست بیاور.

3- ماکسیمم فاصله نقاط مرزی را به ازای همه ی جهت ها برگردان:

diameter = max_a ( ||p_a - q_a|| )

سوال: اگر جهت هایی که در نظر می گیریم بردارهایی باشند که با هم زاویه مساوی می سازند (یکنواخت باشند)، به چندتا از آنها نیاز داریم تا فاصله ی هر بردار دلخواه تا آنها فاصله ی حداکثر delta داشته باشد؟ (در فضای d-بعدی)

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

3D:

a=(teta_i, teta_j,teta_k)

v=(a_i,a_j,a_k)

a-v =(teta_i-a_i, teta_j-a_j, teta_k-a_k)

||a-v|| = sqrt( (teta_i-a_i)^2+(teta_j-a_j)^2+(teta_k-a_k)^2) = delta

d-dimensions:

delta_teta = sqrt(1/d)*delta

که delta_teta زاویه بین دو بردار متوالی در هر بعد است. پس تعداد کل بردارهای لازم:

#vectors in 2-d = 2*pi/delta_teta = 2*pi*sqrt(d)/delta

#vectors in d-dimensional space = (#angles in each plane from each base vector)^(d-1)

= (2*pi*sqrt(d)/delta)^(d-1)

= O( 1/delta^(d-1) )

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

*محاسبه ضریب تقریب الگوریتم

فرض کنید قطر بهینه بین نقاط p و q باشد.

تصویر بردار p به q را روی بردار a می خواهیم به دست بیاوریم. (برای این کار می توانیم ضرب داخلی دو بردار را حساب کنیم چون بردار a یکه است.)

|q_a-p_a| >= (q-p).a = |q-p|.|a|.cos (teta) = |q-p|.cos(teta)

(0<= teta <= delta ==> cos(delta) <= cos(teta) <= 1 )

projection >= |q-p|.cos(teta) >= |q-p|.cos(delta)

ALG >= OPT.cos(delta)

( cos(delta) > 1-(delta^2)/2 )

OPT >= ALG >= OPT.(1-(delta^2)/2)

factor: 1-epsilon

(epsilon = (delta^2)/2)

*زمان اجرا

=هزینه ی تصویر کردن نقاط در این بعدها

#points * #directions = n*1/O(epsilon^((d-1)/2)) = O( n/epsilon^*(d-1)/2) )

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

ایده: ترکیب الگوریتم های 2 و 3 برای به دست آوردن تقریب بهتر

الگوریتم:

1) رند کردن نقاط به نقاط توری (الگوریتم 2)

2) رند کردن نقاط جدید در جهت های مختلف (الگوریتم 3)

*ضریب تقریب الگوریتم

ضریب تقریب آنها در هم ضرب می شود:

(1-epsilon)(1-epsilon)=1-2epsilon=1-epsilon'

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

step1: O( n+1/epsilon^(d-1) ), n'=#grid_pts = 1/epsilon^(d-1)

step2: O(n'*1/epsilon^(d-1)/2)

O( n+1/epsilon^(d-1)+1/epsilon^(d-1)*1/epsilon^(d-1)/2) = O(n+1/epsilon^(3(d-1)/2) )

5-الگوریتم چان

ایده:

-قدم آخر الگوریتم 2 را به صورت بازگشتی روی d حل کنیم.

-زیرمساله کلی تری را حل کنیم: دیاگرام ورونوی گسسته (DVD)

**دیاگرام ورونوی گسسته

تعریف مساله: مجموعه ای P از n نقطه از رئوس توری d بعدی u x u داده شده است، به ازای هر نقطه q کوئری (dبعدی) دورترین همسایه از q را از بین نقاط P پیدا کنید.

راه حل معمولی: امتحان کردن همه ی حالت ها:

O(n^2)

#points = n <= #grid points = u^d

O( u^(2d) )

مشاهده: دورترین همسایه نسبت به نقطه = دورترین همسایه نسبت به راس توری متناظر آن نقطه

اثبات:

نقطه q، دورترین همسایه p، راس توری متناظر نقطه q^

اثبات با شکل: فرض کنید وسط لابی دانشکده ایستاده اید، سر شما نقطه q است و دورترین نقطه در صفحه ی کف دانشکده (که توری هم هست!) نقطه ی p است و پای شما نقطه ی q است. هر نقطه ای که در صفحه ی کف دانشکده نسبت به سر شما دورترین باشد، نسبت به پای شما هم دورترین است.

(فرض کنید روی یکی از راسهای توری ایستاده اید چون کلا مساله گسسته است)

الگوریتم دیاگرام ورونوی گسسته: (d بعد، مجموعه نقاط P)

1) دیاگرام ورونوی گسسته را برای صفحه های توری عمود بر محور d به دست بیاورید. (همین تابع را با d-1 صدا کنید.)

2) برای هر خط عمودی توری L، دورترین همسایه هایی که در مرحله ی 1 نسبت به این خط پیدا کرده اید (چون در مرحله قبل برای همه ی خطوط توری حساب کرده بودیم)، S_L بنامید.

3) برای هر نقطه توری q روی خط L، دورترین همسایه ی q از اعضای S_L را گزارش کنید.

تحلیل:

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

u^(d-1) = #grid cells in (d-1) dimensions (u x u grid)

u = #points in current dimension

u = finding the farthest point in u (d-1)-hyper-plane (grid)

==> T(d,u) = u*T(d-1,u)+O(u^(d-1)*u*u)

T(1,u) = O(u^2)

T(d,u) = O(u^(d+1))

*زمان الگوریتم قطر 4 (چان)

(در مرحله ی آخر الگوریتم 2(توری) از دیاگرام ورونوی گسسته استفاده کرد.)

u=1/epsilon d'=d-1==>d'+1=d

O(n+1/epsilon^d)

*ضریب تقریب مثل قبل.

*بهترین الگوریتم فعلی:

O( n+1/epsilon^(d-3/2) )

Open problem: O( n+1/epsilon^((d-1)/2) )