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