رنگ‌آمیزی بدون تداخل برای مستطیل‌های متحرک

جموعه‌ی s متشکل از n ناحیه با نوعی ثابت (مانند دایره‌ها یا مستطیل‌های موازی محور) مفروض است. یک رنگ‌آمیزیِ بدون تداخل برای s اختصاص رنگ به ناحیه‌هاست به گونه‌ای که برای هر نقطه‌ی p‎ که حداقل یک ناحیه از s شامل آن باشد، ناحیه‌ای وجود داشته باشد که رنگ آن در میان تمام ناحیه‌های مشمول ‎ pیکتا باشد. هدف ما در این مقاله، نگه‌داری رنگ‌آمیزی بدون تداخل برای مستطیل‌ها در حالت متحرک است. ناحیه‌ها در حال حرکت هستند، پس بعد از برخوردِ دو ناحیه، ممکن است رنگ‌آمیزی دیگر بدون تداخل نماند و نیاز به تغییر رنگ تعدادی از ناحیه‌ها باشد. هدف ما کمینه کردن تعداد رنگ‌های استفاده شده، تشخیص زمان‌های برخورد و همچنین کمینه کردن تعداد ناحیه‌هایی است که بعد از برخورد مجدداً رنگ‌آمیزی می‌شوند. در این پژوهش، مسئله‌ی رنگ‌آمیزی بدون تداخل را برای مستطیل‌های متحرک در صفحه و همچنین مستطیل‌های متحرک روی محور طول‌ها بررسی کرده‌ایم. الگوریتمی برای رنگ‌آمیزی بدون تداخل مستطیل‌های متحرک در صفحه ارائه می‌کنیم که از o(log^4(n))رنگ استفاده می‌کند و برای هر رویداد o(log(n)) رنگ‌آمیزی مجدد انجام می‌دهد. همچنین برای مستطیل‌های متحرک بر روی محور، الگوریتمی با استفاده از o(log^2(n)) رنگ و (log(n))o رنگ‌آمیزی مجدد برای هر برخورد ارائه می‌دهیم.‌