مقدمات - هندسه محاسباتی پیشرفته

مرجع: 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 برابر جواب بهینه است، (چون دایره ی جواب شامل تقاطع هست.)