هندسه پیشرفته (مرور جلسه دوم)

الگوریتم‌های جلسه قبل از مرتبه O(dn) بودند یعنی برای ابعاد بالا قابل استفاده نیستند. پس یک بار دیگر عملکرد الگوریتم‌های جلسه قبل را بررسی می‌کنیم.

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

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

ما عمل مقیاس کردن را در روش توری انجام دادیم و روش تصویر کردن جهتی را هم الآن بررسی کردیم. می‌توانیم این دو را ترکیب کنیم چون خروجی الگوریتم توری یک مجموعه نقاط است و می‌توان مجدداً روی آنها الگوریتم دیگری اجرا کرد. با این کار تقریب مورد نظر به هم نمی‌خورد چون نقاط درون یک خانه‌ی توری از نظر زاویه به هم نزدیک هستند. در غیر این صورت باید ضریب تقریب‌ها را جمع می‌کردیم و ضریب تقریب دو برابر می‌شد.

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

من الآن دارم مقاله را می‌خوانم و حس می‌کنم این‌ها هیچ ربطی به مطالب مقاله ندارند.