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 است.