مقدمات- هندسه محاسباتی پیشرفته -بخش 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)