علوم رایانش و فناوری اطلاعات

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

نویسندگان

دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف، تهران، ایران

چکیده

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

کلیدواژه‌ها

  • [1] S. Smorodinsky. Combinatorial Problems in Computational Geometry. PhD thesis, School of Computer Science, 2003.
  • [2] G. Even, Z. Lotker, D. Ron, and S. Smorodinsky. “Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks.” SIAM Journal on Computing, 33(1):94– 136, 2003.
  • [3] T. Leijsen. Kinetic conflict-free coloring. Master’s thesis, Eindhoven University of Technology, the Netherlands, 2014.
  • [4] J. Basch, L. J. Guibas, and J. Hershberger. “Data structures for mobile data.” Journal of Algorithms, 31(1):1–28, 1999.
  • [5] J. Basch and L. J. Guibas. Kinetic data structures. PhD thesis, Department of Computer Science, Stanford University, United States, 1999.
  • [6] L. J. Guibas. “Kinetic data structure: a state of art report.” In Workshop on Algorithmic Foundations of Robotics, pages 191–209, 1998.
  • [7] J. Pach and G. Tóth. “Conflict-free colorings.” In Discrete and computational geometry, pages 665–671. Springer, 2003.
  • [8] S. Har-Peled and S. Smorodinsky. “Conflict-free coloring of points and simple regions in the plane.” Discrete & Computational Geometry, 34(1):47–70, 2005.
  • [9] K. M. Elbassioni and N. H. Mustafa. “Conflict-free colorings of rectangles ranges.” In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, pages 254–263, 2006.
  • [10] D. Ajwani, K. M. Elbassioni, S. Govindarajan, and S. Ray. “Conflict-free coloring for rectangle ranges using 〖O(n〗^0.382) colors.” Discrete & Computational Geometry, 48(1):39–52, 2012.
  • [11] M. de Berg, T. Leijsen, A. Markovic, A. van Renssen, M. Roeloffzen, and G. J. Woeginger. “Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points.” In 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, pages 26:1–26:13, 2017.
  • [12] M. de Berg and A. Markovic. “Dynamic conflict-free colorings in the plane.” Computational Geometry, 78:61–73, 2019.
علوم رایانش و فناوری اطلاعات
دوره 18، شماره 1
بهار و تابستان
اردیبهشت 1399