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

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

لم: فرض کنید قطر 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!) بین فضا و زمان

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

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

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

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