جلسه هفتم هندسه محاسباتی پیشرفته
*کوچکترین دایره محیطی
مجموعه 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 گفته بود اما اینجا به ازای مرکز دایره ی بعدی و این دایره گفته است. الآن جا دارد مثل روزنامه ها بزنم عکس تزئینی است! :)) }
خلاصه بقیه داستان: ارتباط شعاع دو مرحله متوالی را به دست می آورد و شرط خاتمه را هم بر حسب شعاع می نویسد. با استفاده از آن ارتباط شعاع دو مرحله متوالی را به دست می آورد. با استفاده از آن و شرط خاتمه تعداد دفعات تکرار لازم برای رسیدن به جواب را به دست می آورد.
بعد هم خوشحال می شود که یک هسته برای کوچکترین توپ محیطی به دست آورده است که از تعداد ابعاد مستقل است. بعد از آن برای به دست آوردن جواب مساله استفاده می کند.
