تمرینات 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.

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

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