مرکزهای متحرک

دلیل اینکه مرکز دایره قبلی و جدید روی هم قرار می‌گیرد این است که دو دایره حتما بر هم مماس می‌شوند در نتیجه همیشه حالت قطر اتفاق می‌افتد.

تقریب بدیهی دایره محیطی با عرض

این جوابی بود که سر کلاس تی‌ای هم داده شد:

کتاب هارپلد (فصل ۲)

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

زمان ساخت درخت از اینجا n log phi به دست می‌آید. (phi = نسبت قطر به عرض)

درخت فشرده

برای رسیدن به زمان لگاریتمی بر حسب n باید از مسأله فصل قبل استفاده کنیم و توری مناسب را بسازیم. با این کار اندازه خانه‌ای که باید نقاط را بر حسب آن به دو قسمت تقسیم کنیم به دست می‌آید. ثابت می‌شود که این تقسیم نقاط را تقریبا نصف می‌کند.

*درخت چهارتایی فشرده برای مکان یابی نقطه

جستجوی دودویی روی عمق درخت

*

کتاب هارپلد (فصل ۱)

*نزدیک‌ترین زوج نقاط

اگر دو نقطه درون یک خانه توری بیفتند فاصله‌ی آنها از اندازه خانه توری کمتر است. می‌توانیم همین کار را برای خانه‌هایی که تراکم نقاط بیشتر دارند تکرار کنیم. نسخه تصمیم گیری مسأله فقط می‌خواهد بگوییم جواب از یک مقدار کمتر است یا بیشتر که این کار را با ساخت توری انجام می‌دهیم. جستجوی دودویی روی این مقدار جواب را می‌دهد.

بهبود: جایگشت تصادفی از نقاط را حساب می‌کنیم. به صورت افزایشی نقاط را اضافه می‌کنیم و جواب را به دست می‌آوریم. اگر از قبل بهتر شده بود توری را مجدداً می‌سازیم. (با توجه به مقدار جدید). این کار زمان O(i) در مرحله i-ام می‌گیرد. چون این احتمال 1/i است پس متوسط زمان اجرا

sum i*1/i = sum 1 = n

یعنی خطی است.

*الگوریتم ۲-تقریبی برای دیسک شامل k نقطه

یک توری تطبیق پذیر را به این صورت می‌سازیم که هر قسمت شامل k نقطه باشد و هر کدام از این قسمت‌ها را به قسمت‌های k/4 نقطه دار تقسیم می‌کنیم.

برای این کار از الگوریتم پیدا کردن عنصر با رتبه مشخص استفاده می‌کنیم که زمان O(n log n/k) می‌گیرد که O(n) برای قسمت اول است و در قسمت دوم چون بازگشتی تا جایی پیش می‌رویم که k/4 نقطه بماند زمان آن O(log n/k) می‌شود.

سپس برای هر خانه از رئوس توری کوچکترین دایره شامل k نقطه را پیدا می‌کنیم.

تعداد رأسهای توری (n/k)^2 تا است و برای پیدا کردن کوچکترین دایره شامل نقاط به چک کردن بیش از n نقطه نیاز نخواهیم داشت. پس کلاً زمان O(n (n/k)^2) می‌گیرد.

هر دایره برای اینکه k نقطه داشته باشد باید حداقل ۴ ناحیه را قطع کند. پس حتما شامل یکی از رأسهای توری می‌شود.

بهبود:

با استفاده از توری سلسله مراتبی و ساختاری مشابه skiplist می‌توانیم به زمان خطی برای این مسأله برسیم. این کار را تا جایی ادامه می‌دهیم که k نقطه در آن سطح باقی بمانند.

هیچ خانه توری بیش از 5k نقطه ندارد. (اثبات با رسم ۴ دایره در گوشه‌های خانه توری و دایره محاطی خانه توری+ماکسیمم تعداد نقاطی که در دایره به شعاع خانه توری جا می‌شوند)

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

ساخت skip-list زمان خطی می‌برد. زمان محاسبه جواب برای هر توری O(k) است. با تلاش فراوان (!) زمان متوسط خطی به دست می‌آید.

*حل تمرین‌های فصل ۱

http://softday.blog.ir/1392/11/21/%D8%AA%D9%85%D8%B1%DB%8C%D9%86-%D9%87%D8%A7%DB%8C-%D9%81%D8%B5%D9%84-1-%DA%A9%D8%AA%D8%A7%D8%A8-%D9%87%D9%86%D8%AF%D8%B3%D9%87-har-peled

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

کتاب هارپلد رو بخونید! تقریباً همه‌ی تمرین‌ها از این کتاب بوده!

تمرینات quad tree از کتاب هندسه محاسباتی

پیدا کردن همسایه یک خانه درخت چهارتایی

حل تمرین از متن کتاب:

14.4 Let P be a set of point in 3-dimensional space. Describe an algorithm to

construct an octree on P. (An octree is the 3-dimensional variant of the

quadtree.)

جواب:

هر بار مکعب قبلی را به ۸ قسمت (از هر ضلع نصف) تقسیم می‌کنیم و نقاط درون هر قسمت را به دست می‌آوریم و به صورت بازگشتی برای آنها درخت را می‌سازیم. شرط خاتمه این است که تعداد نقاط کمتر مساوی ۱ باشد.

14.10 A quadtree can also be used to store a subdivision for efficient point lo-

cation. The idea is to keep splitting a bounding square of the subdivision

until all leaf nodes correspond to squares that contain at most one vertex

and only edges incident to that vertex, or no vertex and at most one edge.

a. Since a vertex can be incident to many edges, we need an additional

data structure at the quadtree leaves storing vertices. Which data

structure would you use?

b. Describe the algorithm for constructing the point location data struc-

ture in detail, and analyze its running time.

c. Describe the query algorithm in detail, and analyze its running time.

جواب:

hash table که هر برگ درخت را به رئوس متناظر آن ببرد.

راه حل اول (بدون هش): خانه‌ی شامل نقطه کوئری را پیدا می‌کنیم و در آن point location انجام می‌دهیم. در این صورت زمان ما از مرتبه تعداد رأس‌های درون خانه شامل نقطه کوئری خواهد بود.

راه حل دوم: برای هر خانه مجدداً تقسیم بندی مشابه درخت چهارتایی را انجام بدهیم با این تفاوت که هر خانه را به رأس متناظر آن هش کنیم. در این صورت با تقسیم مختصات نقطه کوئری و جزء صحیح گرفتن از آن به خانه‌ی جدول هش می‌رسیم و ناحیه متناظر آن را گزارش می‌کنیم. برای پیدا کردن برگ شامل نقطه کوئری از جستجوی دودویی استفاده می‌کنیم تا نیاز نباشد کل عمق درخت را برویم.

14.13 Quadtrees can be used to perform range queries. Describe an algorithm

for querying a quadtree on a set P of points with a query region R.

Analyze the worst-case query time for the case where R is a rectangle,

and for the case where R is a half-plane bounded by a vertical line.

برای کوئری نیم صفحه قسمت خط عمودی که ساده است و برای قسمت خط مورب باید همه‌ی خانه‌هایی که این ضلع آنها را قطع می‌کند و همه‌ی خانه‌های بین دو خط را چک کنیم.

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

کوچکترین توپ محیطی با روش مرکزهای متحرک

(مقاله دکتر ضرابی زاده)

حالتی که در پست قبلی در این مورد نوشته بودم به این دلیل در تحلیل آمده است که بدترین حالت مسأله است و بدیهی است که همیشه برقرار نیست.

در شکل بالا همیشه اگر از p3 به نقطه مماس وصل کنیم، چون شعاع در نقطه تماس بر خط مماس عمود است اگر از c1 بگذرد از c2 هم می‌گذرد. در غیر این صورت یک نقطه‌ی دیگر روی محیط دایره دوم باید باشد تا این دایره کوچکترین دایره محیطی باشد. (حالت دو سر قطر اتفاق نمی‌افتد.)

این حالتی است که در آن دایره در هر مرحله (اضافه شدن هر نقطه) بزرگ‌تر می‌شود، یعنی همیشه حالتی اتفاق می‌افتد که نقاط دو سر قطر دایره محیطی هستند. فقط می‌ماند اثبات اینکه این بدترین حالت است.

جوابی که این الگوریتم می‌دهد ۳/۲-تقریبی است برای کوچکترین دایره محیطی نقاط و خود الگوریتم هم به این صورت است که به جای اینکه نقطه جدید و نقاط قبلی را در نظر بگیرد نقطه جدید و دایره محیطی قبلی را در نظر می‌گیرد و کوچکترین توپ محیطی آن را حساب می‌کند.

اثبات قدم زدن تصادفی با spanner تتا گراف

کلا ربات ۸ تا سنسور دارد که هر کدام یک بازه‌ی مساوی را می‌بینند. (یک دایره است که به ۸ قسمت تقسیم شده است.)

این ۸ همان مقدار لازم برای همبند بودن تتا گراف است.

به این صورت گراف متناظر آن ساخته می‌شود و بقیه اثبات مثل random walk معمولی است.

حل سوال ۳ سری اول خودم (هندسه پیشرفته)

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

هسته با روش دو برابر کردن (جویباری)

*روش دو برابر کردن معمولی

تقریب عرض جهتی:

دو نقطه‌ی اول را s و t می‌نامیم. هر بار یک نقطه جدید می‌آید (p) عرض این سه نقطه را حساب می‌کنیم و اگر نقطه جدید از دو برابر نقطه قبلی دورتر بود نقطه جدید را جایگزین قبلی می‌کنیم.

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

*روش قبل را با استفاده از توری و دیاگرام ورونوی گسسته حل می‌کنیم. (مینیمم و ماکسیمم نقاط را نگه می‌داریم.)

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

با استفاده از این روش یک راه کلی ساختن هسته ارائه داده است که یک الگوریتم افزایشی روی تعداد ابعاد است (مثل دیاگرام ورونوی گسسته)‌ که هر بار با استفاده از توری نقاط را روی راستای دورترین دو نقطه تصویر می‌کند. (یعنی قطر فعلی). حداکثر میزان تغییرات مثل قبل به دلیل نصف شدن محدود است.

*بهبود الگوریتم با روش merge and reduce

(با روش رند کردن جهتی اپسیلون-کرنل ساخته می‌شود.)