درخت اشتاینر و مساله فروشنده دوره گرد

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

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

قضیه: می توان مساله ی درخت اشتاینر را به درخت اشتاینر متریک تبدیل کرد بدون اینکه ضریب تقریب به هم بخورد.

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

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

برای هر یال گراف ثانویه هزینه ی آن از هزینه ی یال گراف اولیه کمتر مساوی است. پس هزینه ی جواب روی گراف ثانویه از هزینه ی جواب روی گراف اولیه کمتر مساوی است.

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

الگوریتم درخت اشتاینر متریک:

تا اینجا ثابت کردیم که حالت متریک را حل کنیم حالت معمولی هم حل می شود. حالا می خواهیم حالت متریک را حل کنیم.

MST راسهای لازم را حساب می کنیم و این یک جواب غیربهینه برای مساله است. (چون MST در P است و درخت اشتاینر در NP-hard). اما این جواب غیربهینه فاصله ی کمی تا جواب بهینه دارد (ضریب تقریب 2).

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

مثال tight: گراف با n راس لازم و یک راس اشتاینر را در نظر بگیرید. یال بین راس اشتاینر و راس لازم هزینه ی یک دارد و یال بین دو راس لازم هزینه ی 2 دارد. هر MST در این گراف 2(n-1) هزینه دارد، در حالی که جواب بهینه هزینه ی n دارد.

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

فروشنده دوره گرد: یک گراف کامل با یالهای وزندار نامنفی داده شده است، دور با کمترین هزینه را پیدا کنید که هر راس را دقیقا یک بار ببیند. (این مساله را نمی شود تقریب زد مگر اینکه P=NP باشد)

اثبات: برهان خلف: فرض کنید که یک الگوریتم تقریبی چند جمله ای باشد و ضریب آن را a(n) بگیرید. نشان می دهیم با این الگوریتم می توان تصمیم گیری مساله دور همیلتونی (فروشنده دوره گرد بدون وزن!) را حل کرد که در زمان چندجمله ای np-hard است. ایده ی اصلی کاهش از مساله ی دور همیلتونی به فروشنده دوره گرد است که یک گراف را به یک گراف کامل وزندار تبدیل می کند، به طوری که:

الف) اگر گراف اولیه دور همیلتونی داشته باشد، هزینه ی دور فروشنده دوره گرد بهینه در گراف ثانویه n است.

ب) اگر گراف اولیه دور همیلتونی نداشته باشد، هزینه ی دور فروشنده دوره گرد بهینه در گراف ثانویه بیشتر از a(n).n است.

در حالت الف، هزینه ی جواب بهینه از a(n).n کمتر/مساوی است و در حالت ب بیشتر است. پس می توان از آن برای تصمیم گیری وجود دور همیلتونی استفاده کرد. (پس اگر چنین کاری را بتوان انجام داد مساله ی np-hard را در زمان چند جمله ای حل کردیم.)

نحوه ی کاهش (reduction) هم ساده است. به هر یال گراف اولیه وزن 1 بدهید و برای ساخت گراف ثانویه به بقیه یالهایی که نبوده اند وزن a(n).n بدهید. حالا اگر گراف اولیه دور همیلتونی داشته باشد، هزینه ی جواب در گراف ثانویه n می شود، در غیر این صورت هر دور فروشنده دوره گرد در گراف ثانویه باید از یالی بگذرد که هزینه ی a(n).n دارد و در نتیجه هزینه ی آن از این مقدار بیشتر است.

الگوریتم ساده برای تقریب مساله فروشنده دوره گرد متریک با ضریب 2:

با حذف هر یال از فروشنده دوره گرد به یک MST برای گراف می رسیم، پس کران پایین را MST می گیریم.

الگوریتم:

1- یک MST روی گراف پیدا کن.

2- هر یال را دو برابر کن (بین دو راسی که قبلا یال بوده یک یال دیگر با همان وزن بگذار) و یک گراف اویلری به دست بیاور.

3- یک دور اویلری روی این گراف پیدا کن.

4- دوری را که راسهای گراف را به ترتیب آمدن آنها در دور (با راس تکراری!) اویلری می بیند برگردان.

(فکر کنم بهش میگن گذر، توی متن اصلی tour نوشته بود.)

قدم آخر الگوریتم مثل همان عمل پریدن از راسها است که در مساله ی قبل دیدیم. (به نظر من که همه ی مرحله های الگوریتمش مثل مساله قبل است.)

قضیه: الگوریتم بالا ضریب تقریب 2 برای فروشنده دوره گرد متریک می دهد.

اثبات: (دقیقا همان اثبات مساله ی قبل!)

مثال حالت بد: گراف کامل n راسی که یالهای آن وزنهای 1 و 2 دارند. یالهای بین یک راس v و بقیه راسها را وزن یک می دهیم و بقیه راسها هر کدام به دقیقا یک راس دیگر (به جز راس v) یال با وزن یک دارند و بقیه یالها وزن 2 دارند. پس تعداد یالهای با وزن 1 می شود 2(n-1) که یک ستاره و دور n-1 راسی می سازند. جواب بهینه روی دور حرکت می کند و قبل از اینکه به راس شروع برگردد از راس وسطی عبور می کند. این جواب هزینه ی n دارد. جواب الگوریتم ما MST است که مثلا می تواند گراف ستاره باشد، در این حالت گراف اویلری که از روی آن می سازیم دو یال با وزن 1 دارد و بقیه وزن 2 دارند، که در مجموع هزینه ی 2(n-1) دارد که دو برابر  جواب بهینه است.

بهبود الگوریتم به ضریب 3/2:

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

لم: هزینه ی تطابق کامل یالهای درجه ی فرد (که تعدادشان زوج است چون جمع درجات زوج است) کمتر مساوی جواب بهینه است.

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

قضیه: این الگوریتم ضریب تقریب 3/2 برای فروشنده دوره گرد متریک دارد.

هزینه ی دور اویلری کمتر از هزینه ی MST + هزینه ی تطابق کامل راسهای فرد است؛ که این خودش کمتر مساوی جواب بهینه فروشنده دوره گرد + 1/2 جواب بهینه ی فروشنده دوره گرد است که می شود جمعا 3/2 جواب بهینه.

مثال tight: برای تعداد راس فرد، یک مسیر بسازید بعد هر راس را به راس بعدی نه راس بعدیش (دو تا راس جلوتر) وصل کنید همین کار را از راس آخر به اول هم انجام بدهید. همه ی این یالها را وزن 1 بدهید بعد از راس آخر به راس اول یک یال با وزن ceil(n/2) وصل کنید. MST که الگوریتم پیدا می کند همان مسیر است که هزینه ی n-1 دارد. تنها راسهای فردش هم راس اول و آخر هستند که با یال به وزن ceil(n/2) وصل می شوند. پس جواب الگوریتم می شود (n-1)+ceil(n/2). جواب بهینه هزینه ی n دارد: یال اول را برویم بعد یالهای پرشی را برویم. هزینه جواب الگوریتم 3/2 برابر جواب بهینه است.

(اگر وزن یال راس آخر به اول را بیشتر کنیم تطابق کامل با کمترین وزن که پیدا می شود دیگر این یال نیست بلکه همان جواب بهینه است.)

کوتاهترین ابر رشته (فصل 2)

مجموعه متناهی از الفبا و n رشته s_i از این الفبا داده شده، کوتاهترین رشته s را بیابید که همه ی رشته های s_i زیر رشته آن باشند. بدون از دست رفتن عمومیت مساله فرض کنید هیچ رشته ای زیر رشته ی دیگری نباشد.

راه حل حریصانه: دو رشته با بیشترین اشتراک را اول قرار بدهیم، بقیه رشته ها را چک کنیم و رشته ای که پیشوند آن با پسوند رشته ی فعلی اشتراک بیشتری دارد انتخاب کنیم و همین کار را ادامه بدهیم.

تحلیل: رشته ها را از نقاط اشتراک آنها با رشته ی بعدی بازه بندی می کنیم. در این صورت هر رشته به حداکثر سه زیر رشته تقسیم می شود: قسمتی که با رشته ی قبل از خود اشتراک دارد، قسمتی که با کسی اشتراک ندارد و قسمت بعد که با رشته ی بعدی خود اشتراک دارد. جوابی که برای هر رشته به دست می آید حداکثر دو برابر جواب بهینه ی این دو رشته است. (مثال حالت بد: سه رشته ی cb...b و b...ba و b...b را که طول مساوی دارند در نظر بگیرید، اگر دو رشته اول را به هم بچسبانیم و بعد رشته ی فقط b را بگذاریم جواب cb..bab...b است که دو برابر حالتی است که اول فقط b را به یکی از رشته های دیگر بچسبانیم یعنی cb..ba.)

از اینجا نتیجه می شود الگوریتم حریصانه ی قبلی ضریب 2 دارد و خوب نیست. حالا سعی می کنیم آن را بهبود بدهیم.

راه حل حریصانه 2: با حذف ترتیب انتخاب مجموعه ها می توانیم انتخاب حریصانه ی بهتری انجام بدهیم. همه ی ابررشته های ممکن را برای هر دو رشته ورودی حساب می کنیم (نه فقط دو تا ابر رشته ی بهینه ی آنها را، نمی دانم چرا؟؟).

طبق تعریف ابر رشته ی بهینه، همه ی رشته های دیگر زیر رشته ی آن هستند و این ابررشته کمترین طول را دارد. پس ما می توانیم هزینه ی هر ابررشته ی زوج رشته {همان اجزای مساله که می گفتم} را تعداد زیرمجموعه های آن بگیریم. با این کار هنگام ادغام دو جواب مرحله ی قبل، با اجتماع گرفتن مجموعه ها به مجموعه ای می رسیم که زیر رشته های رشته های سازنده ی چند ابررشته است.

پس به حالتی از مساله ی پوشش مجموعه ای رسیده ایم که تعدادی مجموعه داریم (ابر رشته ی زوج رشته ها) که شامل زیر رشته های این ابررشته ها هستند و می خواهیم مجموعه ی مرجع همه ی زیرمجموعه های همه ی رشته ها را بپوشانیم. هزینه ی هر مجموعه هم تعداد زیر رشته های درون آن است.

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

(توی کتاب نگفته که چرا ابر رشته ها رشته مشترک ندارند یا اگر دارند چطور رشته های مشترک را حذف می کند و کاری می کند که یک رشته بیش از دو بار نیامده باشد.)

جواب نهایی شده ضرب ضریب تقریب این دو مساله: 2 * H(n)

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

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

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