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) می‌گیرد، چون برگ‌های آن هر کدام یکی از خطوط هستند.

epsilon net

http://www.compgeom.com/~piyush/papers/vc-dim.pdf

سوال: بعد VC برای d-ضلعی‌های محدب در صفحه چیست؟

جواب: 2d+1

دلیل؟

weaker cutting lemma

proof of cutting lemma 2

proof of cutting lemma