موازی سازی با پردازنده های کمتر + محاسبات پیشوندی

ساختارهای کوئری هندسی تقریبی

مرجع: http://www.ics.uci.edu/~goodrich/pubs/crc-chap05.pdf

تمرین های فصل 1 کتاب هندسه har peled

1- فرض کنید C و P دو مجموعه از نقاط در صفحه باشند، طوری که |C| = k و |P|=n.

r=max_p_in_P min_c_in_C ||c-p||

قرار دهید r را شعاع پوشا برای P توسط C. (یعنی اگر یک دایره به شعاع r حول هر کدام از نقاط C قرار دهیم این دایره ها همه ی نقاط P را می پوشانند.)

الف) یک الگوریتم با زمان اجرای متوسط O(n+k log n) بدهید که عدد a را برگرداند که a <= r <= 10a. {یک 10 تقریب از شعاع پوشا}

ب) برای هر epsilon >0 که در ورودی داده می شود، یک الگوریتم با زمان متوسط O(n+k/epsilon^2 log n) بدهید که عدد a را برگرداند که a <= r <= (1+epsilon)a باشد.

2- مجموعه P از n نقطه در صفحه و پارامتر k داده شده است. یک الگوریتم تصادفی ساده بدهید که در زمان متوسط O(n (n/k)) یک دایره شامل k نقطه از P برگرداند که شعاع آن کمتر از 2 برابر شعاع بهینه ی پوشاندن k نقطه از P باشد.

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

حل:

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

(هر بار از جواب مرحله قبل برای ساختن توری جدید استفاده می کنیم. اگر نقطه جدید درون خانه ی شامل یک عضو از C افتاد که جواب تغییر نمی کند و در غیر این صورت جواب با زمان O(k) قابل محاسبه است. احتمال تغییر جواب هم مثل قبل 1/i است که i شماره ی مرحله یا به عبارت دیگر تعداد نقاط اضافه شده از مجموعه ی P است.)

2- حل قبلی که برای این مساله داده شد با زمان O(n (n/k)^2) بود و ایده ی آن استفاده از توری غیریکنواخت بود و یک الگوریتم قطعی بود. با ترتیب تصادفی نقاط تقاطع توری را چک می کنیم و هر بار از مینیمم r (شعاع دایره شامل k نقطه) به دست آمده برای چک کردن دایره بعد استفاده می کنیم: تعداد نقاط خانه های مجاور را که فاصله ی کمتری از شعاع فعلی دارند بررسی می کنیم اگر کمتر بود جواب تغییر نمی کند.

ادامه ی درخت چهارتایی

کران برای ارتفاع درخت

لم: فرض کنید قطر P (بیشترین فاصله ی زوج نقاط P) بیشتر از 1/2 باشد. (نقاط درون یک مربع یک در یک هستند). در این صورت ارتفاع درخت از مرتبه قطر نقاط به عرض نقاط خواهد بود.

اثبات: (مال خودش سخت بود مال خودم رو می نویسم!)

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

نتیجه:

اندازه ی ساختمان داده: O(|P| log diameter/width)

زمان ساخت: O(|P| log diameter/width)

زمان کوئری: O( log log diameter/width)

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

آیا از این بهتر هم می شود؟

* درخت چهارتایی فشرده شده

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

زمان آن به نسبت قطر به عرض وابسته است.

هر گره میانی حداقل دو فرزند دارد. تعداد گره های درخت کمتر از 2*تعداد برگها-1 است که تعداد برگها=تعداد نقاط.

سوال: چطور درخت T را بهینه بسازیم؟

سوال: چطور مکان یابی نقطه را با آن بهینه انجام بدهیم؟

*ساخت درخت چهارتایی فشرده

ساخت درخت چهارتایی غیرفشرده می تواند زمان نامتناهی بگیرد. (؟)

الگوریتم توان 4: (ساخت درخت)

1- برای هر زوج نقطه بزرگترین مربع شامل آنها را پیدا کنید. این یک گره از درخت خواهد بود. برای هر گره از درخت حتما این زوج نقطه وجود دارند.

این مرحله لیست گره های میانی را می سازد. (کامل)

2- برای هر گره در لیست، آخرین جد آن (در لیست) را پیدا کنید و آن را به این گره وصل کنید.

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

الگوریتم بهتر: (ساخت درخت)

k = |P|/10

دایره ی شامل k نقطه را پیدا کنید (الگوریتم 2-تقریبی که برای پیدا کردن کوچکترین دایره ی شامل k نقطه گفته شد به کار ببرید.)

یک چهارخانه با اندازه ی خانه های کوچکترین توان 2 که از شعاع دایره مرحله قبل بیشتر باشد بسازید.

خانه با بیشترین تعداد نقطه را پیدا کنید (c).

...؟؟

زمان (ساخت) = O(|P| log|P|)

اگر درخت نامتوازن باشد، زمان کوئری بیشتر از |P| می شود. (به نظرم با همون روشهای معمولی متوازن کرده درخت رو.)

زمان کوئری = O(log|T|) = O(log|P|)

* درخت چهارتایی پویا

درخت چهارتایی فشرده ی معمولی (نامتوازن) را می شود به سادگی بهش نقطه اضافه/کم کرد، اما درخت متوازن شده را نمی شود.

شبیه ساخت لیست پرشی (skip list) عمل می کند: هر نقطه از مجموعه پایینی با احتمال 1/2 به مجموعه ی بالایی منتقل می شود.

روی مجموعه های به دست آمده درخت چهارتایی فشرده (معمولی) بسازید.

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

نحوه کوئری زدن (پیدا کردن نقطه): از بالای سلسله مراتب نقطه ی کوئری را پیدا کنید بروید پایین.

اضافه کردن نقطه: جای نقطه را پیدا کنید و مسیر را هم نگه دارید. در پایین ترین سطح نقطه را اضافه کنید و با احتمال 1/2 بالا ببرید. (مشابه لیست پرشی)

پاک کردن نقطه: مسیر را پیدا کنید، از پایین ترین سطح حذف کنید، سطح ها را تا جایی که خانه ی خالی هست پاک کنید، جایی که یک نقطه ماند تبدیل به برگ کنید.

متوسط زمان همه ی این کارها هم لگاریتم تعداد نقاط است.

* غیرتصادفی کردن درخت چهارتایی پویا

ساخت لیست پرشی 1-2-3 قطعی (؟) + اشاره گرهای دو طرفه بین نقاط مجموعه در لیست و درخت

* درخت چهارتایی متوازن

ساخت مش تطبیقی: کوچکترین مثلث بندی از نقاط را بسازید که کمترین زاویه ی آن کراندار باشد، با این شرط که هر نقطه ورودی یک راس مثلث بندی باشد.

ایده: درخت چهارتایی فشرده ی نقاط را بساز O(|P|log|P|)

آن را غیرفشرده کن.

تا جایی که نقطه ی دیگری در مربع نیفتند آن را با ادغام خانه های اطراف بزرگ کن.

نقطه های تقسیم کننده مربع های مرحله قبل را به درخت اضافه کن.

درخت را متوازن کن.

آنها را با روش رند کردن ناگهانی (snap rounding) رند کن. (برای پاره خط ها است.)

http://doc.cgal.org/latest/Snap_rounding_2/index.html

خانه ها را مثلث بندی کن.

زمان: O( |P| log|P| + |output|)

*جمع بندی

درختهای چهارتایی در مقایسه با چهارخانه های یکنواخت: داد و ستد (trade off!) بین فضا و زمان

ساختمان داده کارا برای مکان یابی در ابعاد پایین، چه در حالت ایستا (درخت چهارتایی فشرده) و چه در حالت پویا (درخت چهارتایی پرشی)

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

ایراد: نامنظم نسبت به جهات: مکان یابی نقطه در بین مثلث ها، مش ها، ...

ابزار قوی رند کردن: رند کردن ناگهانی

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

مرجع: http://graphics.stanford.edu/courses/cs468-06-fall/Slides/nikola.pdf

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

هدف کاهش ثابت بر حسب epsilon ورودی در مساله ی نزدیک ترین همسایه است.

برای این کار از ساختمان داده ای به نام BBD-tree که مخفف Balanced Box Decomposition tree است، استفاده می کند. با داشتن نقطه کوئری و شعاع، پیدا کردن نقاط درون توپ به مرکز نقطه کوئری و حداکثر دو برابر شعاع ورودی زمان O(log n) می برد.

برای جستجوی بازه ای در d-1 بعد از BBD-tree که d-بعدی باشد استفاده می کنیم.

تغییر یکی از موضوعات وبلاگ

احتمالا بخوام تقریبی رو حذف کنم. هم بخوام خودم بخونم هم تهش به همه بیشتر از من نمره بده اصلا ارزش نداره.

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

مرجع: http://graphics.stanford.edu/courses/cs468-06-fall/Slides/steve.pdf

درخت چهارتایی: چهارخانه های سلسله مراتبی

1- فهرست

قطعی:

-مثال ها و نتایج اولیه

- نسخه ی ایستا: درخت چهارتایی فشرده

تصادفی:

- نسخه پویا: درخت چهارتایی پرشی

قطعی:

مش تطبیقی: درخت چهارتایی متوازن

2-مثال اولک مکان یابی نقطه

هدف: یک نقشه مسطح M داده شده که بازه ی 

[0,1)^2

را افراز می کند، M را طوری پیش پردازش کنید که به ازای هر نقطه ی کوئری q در بازه ی 

[0,1]^2

ناحیه شامل q را در زمان خطی (sublinear) پیدا کنید.

2- ادامه مکان یابی نقطه

نواحی را مثلث بندی کنید.

3- ادامه مکان یابی نقطه

درخت چهارتایی T را بسازید که برگهای آن حداکثر با 9 مثلث تلاقی دارند.

4- ادامه مکان یابی نقطه

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

5- ادامه مکان یابی نقطه

(همه ی مربع های مرحله ی قبل دوباره به 4 ناحیه تقسیم شده اند و فرزندان مربع مرحله قبل شان شده اند.)

6- ادامه ی مکان یابی نقطه

(تا برقرار شدن شرط برگ حاوی 9 مثلث تقسیم ادامه داده شده است.)

7- ادامه ی مکان یابی نقطه

(هر برگ متناظر یک خانه ی چهارخانه ای است که در شرایط گفته شده صدق می کند.)

8- ادامه ی مکان یابی نقطه

نحوه ی کوئری زدن: نقطه ی q داده شده، از ریشه درخت جستجو انجام شده تا به برگی برسد که شامل q است، سپس خانه ی متناظر آن راس را که حداکثر 9 مثلث دارد در نظر می گیرد و جای q را پیدا می کند. این کار به اندازه : O(|L|) زمان: O(h) نیاز دارد.

برای چهارخانه ی معمولی: فضای حافظه ی کل: 2^(2^h) و زمان O(1)

آیا از این بهتر می شود؟

(h ارتفاع درخت است و L مجموعه ی برگها است.)

9- ادامه ی مکان یابی نقطه

level i: grid (1/2)^i * (1/2)^i

node containing q represents cell with lower left corner = ((1/2)^i floor(2^i*qx), (1/2)^i floor(2^i*qy))

-نقاط را در جدول هش می گذاریم.

-به ازای هر نقطه کوئری روی ارتفاع درخت جستجوی دودویی انجام می دهیم:

i = (h_max+h_min)/2

اگر خانه ی شامل نقطه کوئری تهی نبود، بین i و hmax جستجو کن، در غیر این صورت بین hmin و i جستجو کن.

زمان: O(log h)

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

1- مثال2: جستجوی بازه ای

مجموعه متناهی از نقاط در بازه ی 0 و 1 داده شده (P)، آن را طوری پیش پردازش کنید که برای هر مستطیل کوئری r در این بازه، نقاط درون مستطیل (اشتراک r و P) را در زمانی به اندازه تعداد نقاط درون مستطیل می گیرد.

2- مثل قبل درخت را بسازید.

3- در هر برگ یک نقطه است، پس تعداد برگهای درخت |P| است. پس اندازه ی درخت کمتر از h*|P| است (ارتفاع درخت * تعداد برگها)

4- کوئری: از ریشه به برگ برو، هر بار اشتراک مستطیل با خانه ی چهارخانه تهی شد متوقف شو.

زمان پیدا کردن نقاط مستطیل در درخت کمتر از h برابر تعداد نقاط درون مستطیل است. (هر نقطه حداکثر h زمان می خواهد.)

برای h چه کرانی می توان داد؟

5- (اسلاید 16 از 60)

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

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

پروژه هندسه محاسباتی پیشرفته

دریافت
حجم: 193 کیلوبایت

هنوز با این لاتکس؟ فارسی درگیری دارم. تازه هر نسخه ای از نرم افزارهاش هم با اون یکی فرق داره.

باید ارائه ی این را هم آماده کنم. (این داستان ادامه دارد..)

پوشش مجموعه ای - مرجع: motwani

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

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