جواب سوال آخر تمرین سوم هندسه پیشرفته

جواب غلط دانشگاه کرنل: دلیل غلط بودن این جواب اثبات نکردن آن برای زیرمجموعه‌های ۵-عضوی است.

http://www.cs.cornell.edu/courses/cs683/2008sp/lecture%20notes/683notes_0428.pdf

جواب درست علاوه بر کتاب هارپلد که قبلاً گفتم در مقاله‌ی زیر هم آمده است:

http://www.inf.ethz.ch/personal/emo/PublFiles/ElephantsMice_SENSYS07.pdf

*امیدوارم بالاخره نمره‌ی این سوال اصلاح شود.

کاربرد VC-dimension

بعد از عمری بالاخره فهمیدم که کاربرد VC-dimension چیه! اینجا را ببینید:

http://www.cs.cornell.edu/courses/cs683/2008sp/lecture%20notes/lec41notes.pdf

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

من اول معذرت می‌خواهم که موضوع هندسه ترکیبیاتی را در وبلاگ جدا کردم و یک عده پیدا نکرده بودند.

دوم اینکه کیفیت سوالهایی که می‌ذارم روز به روز داره کمتر میشه این سری توی اتوبوس نوشتم و عکس گرفتم. :)

Formann 91 Map Labeling

این قسمت سر کلاس درس داده نشد اما جالب بود به همین دلیل اینجا می‌نویسم.

با توجه به شرط‌های موازی بودن با محورهای مختصات و داشتن یک رأس روی نقاط ورودی، به ازای هر نقطه ۴ مستطیل ممکن داریم.

در حالت کلی گفتیم که مسأله NP-hard است اما اگر اجازه دهیم دو مستطیل از مستطیل‌ها مجاز باشند حل می‌شود.

یکی از این دو حالت مجاز را با xi و دیگری را با xi' نشان می‌دهیم (برای هر نقطه pi). در نتیجه تقاطع دو مستطیل به صورت یک عبارت با دو جمله نشان داده می‌شود. پس به مسأله‌ی 2-SAT تبدیل می‌شود و در زمان خطی از مرتبه تعداد تقاطع‌های مستطیل‌ها حل می‌شود.

لم ۱: اگر مستطیلی بیشتر از ۲۴ مستطیل دیگر را قطع کند جواب نداریم.

نتیجه: تعداد تقاطع مستطیل‌ها ثابت است پس از مرتبه O(n^2) تقاطع داریم. (انتخاب دو مستطیل متقاطع * ۲۴) که این حالت می‌تواند اتفاق بیفتد:

اگر تعداد تقاطع‌های مستطیل‌ها p تا باشد، می‌توان در زمان O(n log n + p) آنها را پیدا کرد و حالت جواب نداشتن را تشخیص داد.

برای این مسأله الگوریتم O(n log^2 n) ارائه شده است و برای حالت خاص آن که مربع‌های هم‌اندازه باشد الگوریتم O(n lg n) وجود دارد.

*الگوریتم برای حالت کلی:

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

*تحلیل:

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

لم: تعداد مربع‌هایی که نقطه‌ای در آنها نیست و مربع حول یک نقطه را قطع می‌کنند حداکثر ۲ است.

ضریب تقریب: طول ضلع مربع‌های الگوریتم حداقل نصف جواب بهینه است.

با توجه به اینکه حداکثر ۲ مربع حول یک نقطه می‌توانند شامل نقطه باشند و لم قبل ثابت می‌شود.

زمان اجرا: در حالت عادی باید O(n^2) شود اما با استفاده از یک sweep که O(n log n) زمان می‌برد و محاسبه‌ی جواب 2-SAT در هر گام که O(n) زمان می‌برد، اگر جوابها را تا پایان رویدادها حساب کنیم و بعداً با باینری سرچ جواب بهینه را پیدا کنیم، می‌توانیم زمان کل الگوریتم را به O(n lg n) برسانیم.

*تعمیم:

با یک تبدیل آفین می‌توان آن را به حالت‌های دیگر هم تعمیم داد.

*اثبات NP-complete بودن:

مسأله‌ی 3-SAT را به این مسأله تبدیل می‌کنیم. نقاط را طوری می‌چینیم که فقط دو مستطیل مجاز داشته باشند که به این حالت‌ها xi و x'i می‌گوییم. در نتیجه برای نقاط مجاور آنها هم جواب به صورت یکتا معلوم می‌شود که به آن هم یک متغیر نسبت می‌دهیم. در نتیجه به ازای هر نقطه متغیر دو قطر و متغیر مستطیل‌های خود آن را باید در نظر بگیریم که در کل ۳ تا متغیر می‌شود. پس اینکه تصمیم بگیریم که n نقطه را می‌توان با مستطیل‌ها پوشاند NP-complete است.

k-level

نسخه‌ی متحرک: یک سری نقطه‌ی متحرک روی یک خط داریم که سرعت آنها ثابت است (در نتیجه معادله‌ی زمان مکان آنها خطی است) می‌خواهیم ببینیم نفر k-ام چند بار عوض می‌شود.

x=vt+x0

متناظر با در نظر گرفتن نمودارهای آنها و بررسی جا به جا شدن‌ها است. (k-level) یعنی قسمتی از نمودار که k خط زیر آن هستند. پس تعداد نقاط k-level تعداد تغییرهای نفر k-ام است.

حالت‌های خاص:

یک مجموعه خط داریم، lower envelope آنها چند یال دارد؟ 1-level را می‌توان در زمان O(n) حساب کرد. (با linear programming)

به طور مشابه برای n-level یا upper envelope.

دوگان مسأله:

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

جواب:

بین هر دو رأس k-level که زاویه محدب دارند، حداکثر می‌توانند همه‌ی خطوط زیر آن بیایند که یک زنجیره محدب با O(k) ضلع می‌سازد.

هر نقطه را به صورت یک رأس و هر خطی که k نقطه را از بقیه جدا می‌کند یک یال در نظر می‌گیریم. (طبق تعریف دقیقاً از دو نقطه می‌گذرد.)

نتیجه: هر خط عمودی O(k) یال گراف را قطع می‌کند.

هدف ما پیدا کردن همه‌ی یالهای گراف است. n/m خط عمودی رسم می‌کنیم که بین هر کدام m نقطه باشد. هر خط حداکثر O(k) یال را قطع می‌کند. درون هر ناحیه حداکثر m^2 یال داریم (گراف کامل). پس در کل داریم:

|E| = O(n/m * m^2 + n/m*k)

m = sqrt(k) ==> |E| = O(n sqrt(k))

که m بالا حالتی که دو جمله مساوی می‌شوند و |E| ماکسیمم می‌شود.

بهبود:

تعداد کل تقاطع‌های یالهای گراف O(n^2) است. تعداد نقاط n است پس تعداد خط‌های گذرنده از آنها n^2 است پس تعداد تقاطع‌های ممکن n^4 است که اتفاق نمی‌افتد.

*** اینجا به قسمتی می‌رسیم که کلاً در کلاس بحث نشد و آن این است که چطور زنجیره‌های محدب ساخته می‌شوند؟

از منفی بینهایت شروع می‌کنیم و خط با i-امین بزرگترین شیب را طی می‌کنیم. تنها تقاطع k-level با k-chain در رأسهای محدب است، چون دو یال مجاور یک رأس مشترک بین k-level و k-chain حتماً در k-level نیستند.

ویژگی‌های زنجیره‌های محدب:

۱- همه‌ی رأسهای k-level با یک رأس محدب پوشانده می‌شوند و برعکس. (رأس جدید نداریم)

۲- زنجیره‌های محدب رأسهای مجزا و غیرتکراری دارند.

۳- همه‌ی arrangement (چیدمان) خطوط زیر k-level را می‌پوشانند. در نتیجه همه‌ی رأسهای چیدمان که زیر k-level هستند نقاط تقاطع دو زنجیره محدب هستند.

۴- همه‌ی خطوطی که در ساخت زنجیره‌ی i-ام نقش دارند lower envelopeشان همان رأسهای زنجیره را دارد.

***

حالا از اینجا نتیجه می‌شود که اگر دو یال تقاطع داشته باشند، نقطه‌ی تقاطع آنها در دوگان خطی است که مماس بر زنجیره‌های گذرنده از آن نقطه‌ها است که نتیجه می‌دهد که هر دوی آنها در یک زنجیره محدب هستند اما این در فضای اولیه به معنی داشتن رأس مشترک است (تقاطع در رأس) که می‌دانستیم وجود ندارد. (تناقض)

پس حداکثر تعداد تقاطع‌های هر دو یال به اندازه‌ی تعداد مماس‌های مشترک این زنجیره‌ها است که اگر بین همه‌ی حالت‌ها جمع کنیم همان تعداد رأسهای چیدمان خطوط است که O(n^2) است. (به صورت دقیق‌تر O(nk) است)

اثبات: حالا با استفاده از لم تقاطع داریم:

O(n+n^2/3 x^1/3) = O(n+n^2/3*(nk)^1/3) = O(nk^1/3) = O(n^4/3)

چون تعداد رأسهای گراف n تا است که تعداد نقاط است و تعداد تقاطع‌های آن هم O(nk) است که از روی دوگان آن که چیدمان خطوط بود به دست آوردیم.

-----------------------------------------------------------------

مسائل مرتبط:

*تعداد یالهای level های کمتر مساوی k چندتا است؟ (در جزوه اشتباهی گفته شده رأسها)

با جمع کردن آنها بر خلاف چیزی که توی جزوه هست حتی به همان کران بد هم نمی‌رسیم.

جواب واقعی O(nk) است که (برای چیدمان) می‌گوید هر رأس حداکثر j^2 تا تقاطع دارد (j تعداد levelها) که کلاً O(nk) رأس دارد (چون هر level حداکثر n تا خط دارد و کلاً k تا level داریم) پس در کل O(nkj^2) است که O(n k^1/3 j^2/3) را می‌دهد. (برای اثبات آن از یک قضیه دیگر خارج از مقاله کمک گرفته بود.)

پس جواب درست این سوال که برای k=j خواسته است O(nk) است.

--------------------------------------------------------------

روش کلارکسون:

از probabilistic method استفاده می‌کنیم که اثبات قضیه با استفاده از احتمال است و اندازه‌ی k-level را حساب می‌کنیم. در زیرگراف تصادفی به دست آمده اندازه‌ی k-level برابر O(nk) به دست می‌آید که با جایگذاری در crossing lemma (لم تقاطع) به O(nk^1/3) می‌رسیم.

(کلاً چیزی از مقاله‌اش سر در نیاوردم)

Map Labeling Problem

(من به طرز عجیبی همیشه این صفحه‌ها را جا می‌انداختم توی جزوه و بار اول است دارم می‌خوانمشان!!)

نسخه ۱: ماکسیمم کردن طول ضلع

می‌خواهیم مربع‌های هم‌اندازه با اضلاع موازی محورهای مختصات داشته باشیم که هر کدام یک رأس از مجموعه نقاط را بپوشانند و طول ضلعشان ماکسیمم شود.

جواب: مسأله NP-hard است و تقریب ۲ دارد و ثابت شده بهتر از آن نمی‌شود.

نسخه ۲: ماکسیمم کردن تعداد مربع‌ها

می‌خواهیم k مربع مجزا داشته باشیم که یک رأس هر کدام از مجموعه نقاط باشد و k ماکسیمم باشد. (در نتیجه یک سری نقاط یک رأس مربع نخواهند بود.)

*دوگان؟

من در جزوه نوشتم که این دو مسأله دوگان هم هستند.

*گراف تقاطع: هر شئ یک رأس است و اگر همدیگر را قطع کنند یک یال بین آنها می‌کشیم.

*نسخه ۲: بیان دیگر آن با گراف تقاطع به این صورت است که بزرگترین زیرمجموعه مستقل در گراف تقاطع مربع‌های با ضلع یکسان با یک رأس از نقاط ورودی

*در گرافهای کلی:

مسأله NP-hard است و تقریب با ضریب بهتر از n^(1-delta) ندارد که به ازای این مسأله مثلاً به جای n مربع یک مربع می‌دهد که در نتیجه یک مربع را هم بدهیم به این ضریب تقریب می‌رسیم.

گراف تقاطع با گراف معمولی فرق دارد (مثال: ستاره ۶ رأسی گراف تقاطع نیست.). فعلاً حالت‌های خاص را بررسی می‌کنیم.

مسأله قبل را به صورت اینکه یک سری مربع داریم و می‌خواهیم آنها را شیفت بدهیم تا یک رأس آنها یکی از نقاط ورودی باشد هم تعریف می‌کنند.

*مسأله در حالتی که الزاماً رأس نباشد و فقط بخواهیم نقاط را با مربع‌ها بپوشانیم.

*الگوریتم تقریبی برای حالتی که نقاط زیرمجموعه‌ای از رأسهای یک توری باشند.

برای این کار L نوار عمودی توری متوالی را با هم در یک دسته می‌گذاریم و جواب بهینه‌ی هر دسته را به دست می‌آوریم که برای کل مسأله هم یک جواب تقریبی است. انجام این کار (تقسیم به L نوار عمودی) به L حالت ممکن است که به صورت تصادفی یکی از اینها را انتخاب می‌کنیم.

تحلیل:

جواب بهینه را در نظر بگیرید. ما در آن همه‌ی مربع‌هایی که خطوط توری را قطع می‌کرده‌اند حذف کرده‌ایم. حداکثر تعداد این مربع‌ها در هر خانه m^2 تا است (m=ضلع خانه‌ی توری) که در کل حداکثر O(n^m^2) می‌شود. (؟)

Tukey depth & Helly's Theorem

عمق نقطه: مینیمم تعداد نقاطی که می‌توان در یک طرف هر نیم صفحه شامل آن قرار داد. (تعریف در صفحه)

Tukey median: نقطه با بیشترین عمق

قضیه Helly: یک مجموعه از شکل‌های محدب اشتراک دارند، اگر و تنها اگر دو به دو اشتراک داشته باشند.

قضیه: depth(Tukey median) >= n/(d+1)

اثبات:

می‌دانیم می‌شود صفحه‌ای ساخت که دقیقاً k نقطه یک طرف آن باشند اما می‌خواهیم هر نیم‌صفحه‌ای این خاصیت را داشته باشد. Ham Sandwich cut

برای این کار صفحه‌های با nd/(d+1) نقطه را برمی‌داریم چون تعداد نقاطی که درون آنها نیستند حداکثر n/(d+1) است، پس اشتراک هر d+1 تای آنها ناتهی است.

قضیه رادون: هر مجموعه از d+2 نقطه در فضای d بعدی را می‌توان به صورت دو مجموعه مجزا نوشت که پوسته‌ی محدب متقاطع داشته باشند. به نقاط درون اشتراک، نقطه رادون می‌گویند.

یک الگوریتم این است که به صورت متوالی convex hull نقاط را حساب کنیم. با این کار عمق همه‌ی نقطه‌ها به دست می‌آید. بدترین حالت این است که هر بار یک مثلث حساب کنیم که O(n*n log n) = O(n^2 log n) میشه.

الگوریتم با استفاده از دوگان: اگر دوگان نقطه‌ها را بگیریم، یک مجموعه خط به دست می‌آید و نقاط یک طرف خط (نیم صفحه) تبدیل می‌شود به خط های یک طرف یک نقطه. پس عمق تبدیل می‌شود به مینیمم تعداد خط های اطراف نقطه. اگر level ها را حساب کنیم، برای به دست آوردن نقطه با عمق k می‌توانیم هر خطی که بین k-level و (n-i( level را برگردانیم. فقط باید min(n-i,k)=k باشد و طبیعتاً باید n-i > k باشد که نتیجه می‌دهد i<n-k باشد.

می‌شود k-level را در زمان n^2 حساب کرد و زمان‌های بهتر هم دارد.

center point

http://en.wikipedia.org/wiki/Centerpoint_(geometry)

A simple proof of the existence of a centerpoint may be obtained using Helly's theorem. Suppose there are n points, and consider the family of closed half-spaces that contain more than dn/(d + 1) of the points. Fewer than n/(d + 1) points are excluded from any one of these halfspaces, so the intersection of any subset of d + 1 of these halfspaces must be nonempty. By Helly's theorem, it follows that the intersection of all of these halfspaces must also be nonempty. Any point in this intersection is necessarily a centerpoint.

epsilon sample & epsilon net

epsilon sample: اگر O(1/eps^2 lg 1/eps) نقطه را به صورت تصادفی یکنواخت برداریم با احتمال زیادی در هر نیم فضا نسبت نقاط حفظ می‌شود.

epsilon net: می‌توان مجموعه‌ای از O(1/epsilon lg 1/epsilon) نقطه برداشت که در هر نیم‌فضا حداقل epsilon*n نقطه باشد.

epsilon net: اگر یک فضای بازه با بعد VC برابر d داشته باشیم، یک epsilon net با اندازه‌ی O(d/eps lg d/eps) دارند و یک epsilon sample با اندازه‌ی O(d/eps^2 lg d/eps) دارند. برای به دست آوردن مجموعه‌های متناظر به همین تعداد نقطه را تصادفی یکنواخت انتخاب می‌کنیم.

مثال: جستجوی بازه‌ای

اگر بازه‌ی مورد جستجو مستطیل‌های با اضلاع موازی محورهای مختصات باشند، با epsilon sample به خطای جمعی epsilon*n می‌رسیم.

مثال: تقریب نقطه مرکزی

نقطه‌ای را از مجموعه نقاط برگردانید که هر نیم‌فضای گذرنده از آن نقطه شامل حداقل 

(1/(d+1) - epsilon) n

نقطه باشد.

یک epsilon sample می‌گیریم و نقطه‌ی مرکزی آن را حساب می‌کنیم و به عنوان تقریب نقطه مرکزی مجموعه نقاط اصلی برمی‌گردانیم.

| (r/(d+1)) / r - |P intersection h| / n | <= epsilon

++

ساختمان داده‌های جنبشی

یک بعدی:

مجموعه‌ای از نقاط داریم که روی یک خط حرکت می‌کنند. مینیمم آنها را در هر زمان گزارش کنید.

معادله حرکت نقاط چندجمله‌ای پیوسته با درجه کم (ثابت‌) است که از نظر مرتبه زمانی همان خط می‌شود. پس یک سری خط داریم که می‌خواهم lower envelop آنها را حساب کنیم.

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

دو بعدی:

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

اگر به صورت معمولی sweep را اجرا کنیم زمان آن زیاد می‌شود، به جای آن می‌خواهیم طوری این کار را انجام بدهیم که از مرتبه‌ی تعداد تغییرهای جواب باشد. به چنین الگوریتمی کارا می‌گویند.

می‌خواهیم تعداد رأسهای نمودار حرکت را به دست بیاوریم (که تعداد eventهای sweep است). فرض کردیم که درجه کم است پس تعداد تغییرهای خود نمودار را کنار می‌گذاریم (خط فرض می‌کنیم). که تعداد آنها برابر تعداد رأسهای lower envelope نمودارها است که چون حرکت‌ها دوبعدی هستند (در صفحه هستند) از مرتبه‌ی O(n^(2+delta)) است.

مشابه sweepهای قبلی باید یک درخت نگه داریم که با آن عمل به روز رسانی را انجام بدهیم. اینجا درختی که نگه می‌داریم شامل تغییرات لازم برای الگوریتم (داخلی) و تغییرات واقعی پوسته محدب (خارجی) است. بقیه مثل حالت یک بعدی است. به هر کدام از گره‌های میانی این درخت یک certificate می‌گویند چون به ما می‌گوید که یک رویداد مجاز است.

فضای لازم برای الگوریتم درخت است که فضای O(n) می‌گیرد، چون برگ‌های آن هر کدام یکی از خطوط هستند.