محاسبه قطر نقاط

http://graphics.stanford.edu/courses/cs468-06-winter/Slides/sid_approximate_diam_etc_winter.pdf

اسلایدهای تیموتی چان

جلسه اول

قطر: تعدادی نقطه در فضای d-بعدی داده شده است، فاصله ی دورترین دو نقطه چقدر است؟

for all p,q in P: diameter = max_p_q (distance(p,q)) = max_p_q( ||p-q|| )

کاربردها: ساده ترین روش برای پیدا کردن شکل نقاط است.

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

1-به دست آوردن فاصله ی همه ی زوج نقطه ها و ماکسیمم گرفتن: O(n^2)

2-استفاده از anti podal pair (زوج خطوط موازی که همه نقاط بین آنها قرار می گیرند): O(nlogn)

- در دو بعد با به دست آوردن پوسته محدب نقاط

3- در سه بعد با روش تصادفی clarkson, shor 1998، روش قطعی Ramos 1991 زمان O(nlogn)

4- در چهار بعد O(n^4/3 polylog(n)) ارائه شده توسط Matousek 1992

5- در d بعد O(n^ (2-2/(ceil(d/2)+1))

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

تعریف جدید مساله: diameter را طوری پیدا کنید که به ازای ثابت c داشته باشیم:

diameter <= diameter_OPT <= c*diameter

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

0- یک نقطه دلخواه از بین نقاط را برداریم و فاصله ی دورترین نقطه از بین نقاط از آن را به عنوان قطر برگردانیم.

زمان: O(dn) : این بهترین زمانی است که برای حل این مساله هست.

ضریب تقریب: 2

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

مزیت الگوریتم: یک بار دیدن داده ها برای آن کافی است. این در الگوریتم هایی که روی جویبار داده (data stream) کار می کنند مهم است.

1- یک نقطه دلخواه از بین نقاط بردار، دورترین همسایه آن را به دست بیاور، بعد دورترین نقطه نسبت به این همسایه را به دست بیاور و فاصله اش را به عنوان قطر اعلام کن.

زمان الگوریتم: O(dn)

برخلاف الگوریتم قبلی دو بار باید داده ها را ببیند.

ضریب تقریب: رادیکال 3

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

نقطه دلخواه را p بگیرید دورترین همسایه آن را q بگیرید و t را دورترین نقطه از دورترین همسایه بگیرید.

می خواهیم بین فاصله ی q و t (جواب الگوریتم) و بیشترین فاصله زوج نقاط (جواب بهینه) یک رابطه به دست بیاوریم.

دایره به مرکز q و شعاع قطر نقاط (به دست آمده از الگوریتم که همان ||q-t|| است) می زنیم. همه ی نقاط درون این دایره می افتند چون t دورترین نقطه به q است. نقطه ی p هم درون این دایره است. از مرکز دایره q به p یک خط رسم کنید تا محیط دایره را قطع کند و از آنجا یک دایره به شعاع قطر به دست آمده از الگوریتم بزنید. این دایره از q می گذرد، چون مرکز آن روی محیط دایره بوده و شعاع آن با شعاع این دایره برابر بوده است. مرکز این دایره دوم را o بنامید.

به ازای هر نقطه از نقاط ورودی مثل x می دانیم فاصله ی آن از o کمتر از جمع فاصله x از p و فاصله p از o است (نامساوی مثلث):

||x-o|| <= ||x-p||+||p-o|| <= ||p-q||+||p-o||=||o-q|| = r = ||q-t||

یعنی همه ی نقاط درون این دایره دوم هم می افتند.

دورترین فاصله ی دو نقطه در اشتراک این دو دایره، فاصله ی نقاط تقاطع آنها است، که رادیکال سه برابر شعاع دایره ها می شود. پس ضریب تقریب رادیکال 3 است.

{اگر به مرکز p و شعاع ||p-q|| دایره می زدیم، همه ی نقاط درون آن بودند چون دورترین نقطه از p نقطه q بود. به جای آن از دایره ای که این دایره به آن مماس داخل بود استفاده کردیم که هم شامل این دایره بشود هم تحلیل ساده تر باشد. در واقع بدترین حالت را در نظر گرفتیم که p دورترین نقطه به q بود علاوه بر t!}

2- الگوریتم Barequet, Har-Peled 1999

ایده: رند کردن نقاط با استفاده از توری {به نزدیک ترین گوشه توری}

{این الگوریتم از الگوریتم های تقریبی است که درون آنها از یک الگوریتم تقریبی دیگر استفاده می شود. همان حالتی که ضریب تقریب ها در هم ضرب می شوند.}

1) یک جواب تقریبی با یکی از الگوریتم های قبلی به دست بیاور. (ضریب تقریب آن را c فرض کنید.)

2) به ازای یک epsilon توری diameter*...*diameter با خانه های به طول epsilon*diameter بساز. (تعداد خانه های توری به این صورت است:)

c*diameter/(epsilon*diameter) *...* c*diameter/(epsilon*diameter) = (c/epsilon)^d

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

4) فاصله ی دورترین نقاط جدید (راسهای توری) را به عنوان قطر برگردان.

زمان اجرا :

تعداد نقاط جدید (رند شده) = حداکثر به تعداد نقاط توری =

(2^d)*(c/epsilon)^d

{دو به توان d تعداد گوشه های هر خانه توری در d بعد است! برای دو بعد می شود 4 گوشه!}

مشاهده می کنیم که تعداد این نقاط به تعداد نقاط ورودی مربوط نیست، در نتیجه ثابت است و زمان الگوریتم شامل ساخت توری و محاسبه جواب به صورت زیر است:

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

که قسمت O(n) مربوط به ساخت توری و قسمت O((1/epsilon)^2) مربوط به اجرای الگوریتم دقیق O(n^2) روی نقاط توری است.

ضریب تقریب: 1+epsilon

اثبات:

فاصله ی هر نقطه تا نقطه ی رند شده ی آن یعنی نزدیک ترین گوشه ی خانه ی توری که یک مکعب d بعدی به طول ضلع epsilon*diameter است، حداکثر به اندازه ی نصف قطر مکعب است (حالتی که نقطه دقیقا وسط مکعب باشد) یعنی:

(epsilon*diameter)*1/2*sqrt(1+1+...+1) = (epsilon*diameter)*sqrt(d)/2

حالا می خواهیم با استفاده از آن تقریب جواب را به دست بیاوریم. برای هر دو نقطه p و q از نقاط اولیه که رند شده ی آنها p' و q' هستند، طبق نامساوی مثلث داریم:

||p-q|| <= ||p-p'||+||p'-q||

||p'-q|| <= ||q-q'||+||p'-q'||

==> ||p-q||-||p'-q'|| <= ||p-p'||+||q-q'|| <= (epsilon*diameter)*sqrt(d)/2*2 = (epsilon*diameter)*sqrt(d)

==> |diameter-diameter_OPT| <= diameter*(epsilon*sqrt(d))

==> diameter_OPT*(1-epsilon*sqrt(d)) <= diameter <= diameter_OPT*(1+epsilon*sqrt(d))

یعنی یک 1+epsilon تقریب برای قطر است.

3-بهبود الگوریتم:

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

ضریب تقریب:

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

روش و اثبات:

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

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

به درخواست یکی از دوستان جزوه هندسه محاسباتی پیشرفته به موضوعات اضافه شد.

موضوع درس هندسه محاسباتی پیشرفته، الگوریتم های تقریبی هندسی، ساختمان داده های هندسی و هندسه ترکیبیاتی است.

VC dimension, epsilon-nets and epsilon-approximation (فصل 12 هارپلد)

تجزیه زوج خوب جدا شده WSPD (فصل 4 هارپلد)

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

مرجع: 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)