مروری بر آنچه گذشت.. (هندسه محاسباتی پیشرفته)

۱- تقریب قطر

*تقریب ضریب ثابت: استفاده از نامساوی مثلث و ... برای به دست آوردن تقریب ثابت+تقریب قطر با دورترین نقطه از یک نقطه

*رند کردن ورودی: نقاط ورودی را به نزدیک ترین رأس توری رند می‌کردیم.

*رند کردن جهت‌ها: یک سری شعاع با فاصله یکسان می‌کشیدیم و در راستای آنها جواب را حساب می‌کردیم. + directional width

*روش ترکیبی: برای به دست آوردن جواب در یک خانه توری از یک روش دیگر استفاده می‌کردیم. (ترکیب دو روش تقریبی)

*دیاگرام ورونوی گسسته: یک توری می‌ساختیم و فقط دورترین نقطه به نقاط توری را پیدا می‌کردیم.

۲- تقریب عرض

*رند کردن در جهت‌ها و LP: رند کردن جهت‌ها و استفاده از LP در مرحله‌ی آخر به جای یک الگوریتم دیگر+ساخت توری تجانس یافته در یک جهت و رند کردن نقاط در آن جهت

*یک تقریب ثابت ساده برای عرض: دورترین نقطه نسبت به پاره خط واصل یک نقطه دلخواه و دورترین نقطه به آن

*اپسیلون-هسته: ساخت هسته با روش افزایشی روی ابعاد و تصویر کردن

*روش سریعتر برای محاسبه هسته: تبدیل آفین (ترکیب خطی برداری)‌+رند کردن به رئوس توری

-موارد دیگر: +دیاگرام ورونوی گسسته +تقریب هسته extent برای همه‌ی توابعی که به پوسته محدب وابسته اند.

۳- مدل جویبار داده (Streaming)

* روش لگاریتمی برای حفظ هسته: هسته دو مجموعه نقطه را به هسته برای اجتماع نقاط تبدیل می‌کند.(برای گستره نقاط)+روش لگاریتمی: ادغام (دو هسته) و کاهش (حذف هسته‌های قبلی)

*روش دوبرابر کردن برای حفظ هسته: نقاط را به صورت افزایشی اضافه می‌کنیم، هرجا تقریب از ۲ بیشتر شد به هسته نقطه اضافه می‌کنیم.

*هسته تقریبا بهینه در مدل جویبار داده:‌ دوبرابر کردن+رسم مجدد توری با اپسیلون جدید در هر مرحله و محاسبه جواب توری جدید از روی قبلی

۴-کوچکترین توپ محیطی

*الگوریتم جویبار داده ساده با ضریب ۳/۲: مرکزهای متحرک (توپ‌های محیطی)

*الگوریتم تکراری +شمای تقریبی (تقریب ۱+اپسیلون): روش مرکزهای متحرک با اضافه شدن دورترین نقاط به جواب قبلی به صورت افزایشی

*هسته با اندازه یک بر اپسیلون برای هر بعدی: بهبود تحلیل روش قبل با محاسبه‌ی حداکثر تغییر در هر مرحله

5-نزدیک‌ترین همسایه تقریبی

*روش جستجوی شعاع ثابت (دو روش ساده مبتنی بر توری): فقط خانه‌های توری که نقطه دارند نگه دار و هنگام کوئری خانه‌های اطراف یک نقطه را به دست بیاور. روش۲: خانه‌های توری اطراف هر نقطه را نگه دار و هنگام کوئری یک دایره شامل نقطه کوئری را از بین همسایگی‌های نقاط برگردان.

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

*کاهش ابعاد با لم JL: تصویر کردن تصادفی و استفاده از توری

۶-تجزیه زوج خوب از هم جدا شده (WSPD)

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

*کاربرد آن در پوشاننده‌ها و درخت پوشای کمینه‌ی اقلیدسی: نسبت کوتاهترین فاصله در گراف به فاصله اقلیدسی حداکثر t باشد به گراف t-spanner می‌گوییم. اگر از زوج‌های خوب جداشده هر دو نقطه را به هم وصل کنیم گرافی که به دست می‌آید ۱+اپسیلون پوشاننده است. درخت پوشای کمینه اقلیدسی را هم با اجرای الگوریتم درخت پوشای کمینه روی پوشاننده می‌توان به دست آورد. (با الگوریتم‌های معمولی MST مثل prim و kruskal)