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

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

روش اول که پیدا کردن دورترین نقطه است از اینجا به ذهن می‌رسد که ماکسیمم فاصله هر دو نقطه قطر را می‌دهد. برای اثبات تقریب باید به ازای هر نقطه p از نقاط اولیه ثابت کنیم که دو نقطه‌ی جواب (مثلا a و b) تقریبی از قطر می‌دهند.

ALG < OPT < c*ALG

max(pa,pb) < ab < pa+pb < 2*max(pa,pb)

یعنی اگر ماکسیمم فاصله‌ از هر نقطه دلخواهی را به عنوان جواب برگردانیم ۲-تقریب جواب بهینه است.

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

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

حالا الگوریتم brute force را روی این نقاط جدید که تعداد کمی دارند (همان طور که گفته شد وابسته به اپسیلون است.) اجرا می‌کنیم که مرتبه‌ی n^2 است و زمان ما همچنان خطی بر حسب n و یک بر اپسیلون خواهد بود. (PTAS) زمان خطی مربوط به رند کردن نقاط به توری است که با یک کف گرفتن (جزء صحیح) انجام می‌شود.

ضریب تقریب آن رادیکال d برابر عرض هر خانه (=قطر هر خانه) خواهد بود که چون تعداد ابعاد را از قبل می‌دانیم می‌توانیم به هر اپسیلون دلخواهی برسیم.

در این توری می‌دانیم که نقاطی که درون مکعب می‌افتند تاثیری در محاسبه‌ی قطر ندارند پس با در نظر گرفتن نقاط روی سطح آن می‌توانیم توان یک بر اپسیلون را در محاسبه‌ی تعداد نقاط یکی کم کنیم.