جواب تمرین هندسه محاسباتی پیشرفته (تمرین ۲)

جوابهای خودم اند.

۱- الف) همان کوئری درخت چهارتایی را می‌زنیم با این تفاوت که در حالتی که قبلاً نقطه را بر‌می‌گرداندیم این‌بار جعبه شامل آن را بر‌می‌گردانیم و در خط آخر الگوریتم که جواب را بر‌می‌گردانیم مینیمم جوابهای دو قسمت را بر‌می‌گردانیم.

ب) قسمت اول: نسبت مساحت قسمتی که مرکز دایره می‌تواند در آن قرار بگیرد به کل خانه را حساب می‌کنیم و این احتمال مورد نظر است.

قسمت دوم: با قسمت قبل و به دست آوردن i با کمک شرط خاتمه به احتمال مورد نظر می‌رسیم.

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

د) جستجوی دودویی+اجرای الگوریتم

ه) جمع مقادیر قسمت قبل است. رابطه‌ی آن قبلاً آورده شده است.

۲- الف) حداکثر ۴ نوار اطراف (راست چپ بالا و پایین) خطا ایجاد می‌کنند پس با قرار دادن ۴*اپسیلون به جای اپسیلون به جواب می‌رسیم. (حکم را در تعداد نقاط هر خانه ضرب کنید.)

ب) روش merge & reduce را به کار ببرید. لگاریتمی بودن را با فرض داشتن n حل کنید.

ج) اپسیلون خلاصه را بسازید و طبق قسمت ب تقریب به دست می‌آید.

*مهلت تحویل تمرین: سه‌شنبه