مرجع: http://graphics.stanford.edu/courses/cs468-06-fall/Slides/natasha.ppt
1-کاربرد توری در تقریب هندسی
-پیشامدهای جالب را محلی و منفرد می کند: نزدیکی محلی است.
-توری های یکنواخت: نزدیک ترین نقطه، k-کمترین دیسک پوشا
-توری های تطبیق دهنده: quadtree
2-نزدیک ترین نقطه
n نقطه داده شده، زوج نقاطی را بدهید که در شرط زیر صدق کنند:
CP =min_p,q in P ||pq||
3-توری برای نقاط
محاسبه ی توری زمان خطی می گیرد.
p=(x,y)
C=id(p) = (floor(x/r),floor(y/r))
( hash(C) = grid cell (C) )
4- یک مجموعه نقطه P و فاصله ی r داده شده است، در زمان خطی بررسی کنید که
CP(P) < r or CP(P) > r
حل:
یک توری با خانه های r x r بسازید.
نقاط را به ترتیب اضافه کنید.
اگر CP(P) < r باشد، pوq در یک خانه یا خانه های مجاور هستند.
می توانیم یک خانه توری را در زمان ثابت بگردیم؟
5-الگوریتم
اگر بعضی خانه ها بیش از 9 نقطه داشته باشند، آنگاه CP(P) <r
الگوریتم:
-خانه ها را به توری اضافه کن.
-اگر cell(p) بیش از 9 نقطه دارد برگردان CP(P) < r
d <= diam(C)/3=sqrt(r^2+r^2) /3 < r
(یک توری مربعی 3 * 3 در نظر بگیرید که اضلاع آن r باشد: درون توری قبلی را دوباره تقسیم کنید. در هر خانه ی این توری اگر بیش از یک نقطه باشد فاصله شان از r کمتر می شود: قطر خانه های توری.)
6- ادامه الگوریتم
در غیر این صورت فاصله ی p و q را برای هر نقطه q در خانه ی شامل p و خانه های اطراف آن حساب کن.
زمان برای هر نقطه ثابت است (چون تعداد نقاط خانه ها کمتر از 9 تا است و کلا 10 خانه باید چک شوند) پس کل زمان الگوریتم O(n) است.
7- نزدیک ترین زوج نقاط
- جایگشتی از n نقطه ورودی را حساب کنید.
- r_i=CP({p1,...,pi})
(نقاط را یکی یکی اضافه می کنیم و فاصله ی زوج نقاط را حساب می کنیم.)
چک کنید r_i < r_(i-1) باشد. (زمان خطی)
-حالت خوب: r(i) = r(i-1): از قبل چهارخانه (توری خیلی ضایع است خدایی) ساخته شده و برای چک کردن O(1) زمان می خواهیم.
-حالت بد: r_i < r(i-1): چهارخانه را دوباره بسازیم که زمان O(i) می برد.
-کران بدیهی: O(nk) وقتی نزدیک ترین زوج نقاط k بار تغییر کنند.
8-تحلیل
متغیر تصادفی Xi=1 اگر فاصله زوج نقاط تغییر نکند، 0 در غیر این صورت
زمان اجرا:
R = 1+sum_2_n(1+i.Xi)
E(R) = E(1+sum_2_n(1+i.Xi))
=n+sum_2_n(i.E(Xi))
=n+sum_2_n(i.Pr(Xi=1))
9- تحلیل (ادامه)
کران pr(xi=1) = pr(ri < r(i-1) )
- احتمال اینکه pi در CP(Pi) صدق کند.
(احتمال این است که نقطه جدیدی که اضافه می کنیم یکی از نزدیک ترین زوج نقاط باشد.)
-متوسط زمان اجرا
E(R) = n+sum_2_n(i.pr(Xi=1)) <= n+sum_2_n(i 2/i) <= 3n
(احتمال اینکه نقطه ی جدید یکی از نزدیک ترین زوج نقاط باشد:
C(i-1,1)/C(i-1,2) =2/(i-2)
حالا این دو تایی که با جواب فرق دارد را بیخیال بشید! )
10- کوچکترین دایره k-شمول!
دایره با کمترین شعاع که k نقطه در آن باشد.
- همه حالت ها را امتحان کنیم: O(n^k)
- تقریبی با ضریب 2.
(فقط یک دایره می خواهد یعنی باید k تا نقطه که دایره ی شامل آنها از همه کوچکتر است پیدا کنیم پس حداکثر برای پیدا کردن هر کدام از نقاط n تا نقطه را چک می کنیم و می شود n^k حالت)
11- چهارخانه غیریکنواخت
نقاط p را به نوارهای افقی با حداکثر k/4 نقطه در هر کدام تقسیم کنید.
- تقسیم کردن (partitioning) بازگشتی روی میانه
- تعداد نوارها O(n/k)
زمان اجرا:
T(n) = n+2T(n/2)
Stop at n < k/4
O(n log(n/k))
(
T(n) = n+2T(n/2) = n+n+4T(n/4)=...=i*n+2^i*T(n/2^i)
n/2^i < k/4 ==> 4n/k < 2^i ==> i = O(logn/k)
)
12- مرکزهای متناهی
ادعا: D_opt(P,k) شامل حداقل یک نقطه تقاطع از G است. (G=چهارخانه، D_opt(P,k)= دایره با کمترین شعاع شامل k نقطه از نقاط P)
اثبات: برهان خلف
(اگر بخواهد شامل هیچ تقاطی از چهارخانه نباشد باید درون یک نوار افقی و عمودی باشد. در هر نوار افقی حداکثر k/4 و در هر نوار عمودی هم حداکثر k/4 نقطه هست که جمعا می شود k/2 نقطه، اما می دانیم دایره ی ما شامل k نقطه است. نمی تواند فقط نوار افقی یا فقط نوار عمودی قطع کند، چون تعداد نقاط دایره از k/4 بیشتر است حتما خطوطی عمود بر اینها هم آن را قطع می کنند.)
13- الگوریتم
برای هر تقاطع چهارخانه به نام g
-کوچکترین دایره به مرکز p شامل k نقطه را حساب کن.
--؟؟
-- متوسط زمان = O(n)
-بهترین کاندید از بین (n/k)^2 نقطه را برگردان.
زمان اجرا:
O(n (n/k)^2 )
14- درستی
جواب الگوریتم حداکثر 2 برابر جواب بهینه است، (چون دایره ی جواب شامل تقاطع هست.)
دریافت