انطباق نقاط دو رنگ و همرنگ با مستطیل ها

فرض کنید S مجموعه ای از نقاط در صفحه باشد به طوریکه هر عنصر آن دارای رنگ یا قرمز یا آبی است. یک انطباق از S با مستطیل یک مجموعه از جفت مستطیل های هم تراز مجزاست به طوریکه هر مستطیل شامل دقیقاً دو نقطه از S است. چنین انطباقی را همرنگ گوییم اگر هر مستطیل شامل نقاط همرنگ باشد، و دورنگ است اگر شامل نقاط با رنگ متفاوت باشد. در این مقاله دو مسأله زیر را دنبال می کنیم : 1) یافتن بزرگترین انطباق همرنگ از S با مستطیل ها. 2) یافتن بزرگترین انطباق دو رنگ از S با مستطیل ها. برای هر مسأله ما یک الگوریتم تقریبی با زمان چند جمله ای فراهم می کنیم به طوریکه یک انطباق با حداقل 1/4 تعداد مستطیل های انطباق بهینه را بسازد. نشان می دهیم که مسأله ی اول ان - پی سخت است اگر که یا مستطیل های منطبق با پاره - خط های هم تراز از محصور شده باشد یا آنکه S در موقعیت کلی باشد، یعنی هیچ دو نقطه از S دارای مختصات x,y یکسانی نباشد. در جلوتر نشان خواهیم داد مسأله ی دوم هم ان - پی سخت است اگر که S در موقعیت کلی باشد. این نتایج ان - پی سختی با نشان دادن تصمیم گیری درباره ان - پی کامل بودن انطباق کاملی که در هر حالت وجود دارد به دست می آید. نتاج تقریبی براساس ارتباط بین مسأله ی ما با مسأله ی پیدا کردن بزرگترین مجموعه ی مستقل در بین مجموعه ای از مستطیل های هم تراز است. در این مقاله یک انطباق نقاط تک رنگ با مستطیل ها و مربع ها و انطباق نقاط دو رنگ با پاره خط ها را توسعه می دهیم. در ادامه از تکنیکمان استفاده کرده و ثابت می کنیم تصمیم گیری درباره انطباق کامل با مستطیل ها در حالتی که نقاط همرنگ باشند ان - پی کامل است.

کلیدواژه ها:

الگوریتم های تقریبی - انطباق همرنگ - انطباق دورنگ - مسائل ان ، پی سخت و ان ، پی کامل