علوم رایانشی

علوم رایانشی

جداسازی چندخطی های رنگی توسط مستطیل های مینیمال

نوع مقاله : مقاله پژوهشی

نویسندگان
1 دانشکده مهندسی کامپیوتر، واحد تهران شمال ، دانشگاه آزاد اسلامی، تهران، ایران
2 دانشیار دانشکده مهندسی کامپیوتر، دانشگاه امیرکبیر، تهران، ایران
10.22034/csj.2025.214935
چکیده
ددو مجموعه رنگی از نقاط (آبی و قرمز)  و  را بر روی صفحه در نظر بگیرید، مسئلة تفکیک‌پذیری نقاط هدف عبارت است از جداسازی نقاط قرمز از نقاط آبی توسط یک مستطیل مینیمال به‌طوری که همه نقاط آبی در داخل مستطیل و همه نقاط قرمز در خارج از مستطیل قرار بگیرند. مستطیل مینیمال برای مجموعه نقاط  مستطیلی است که هر چهار ضلع آن بر بدنه محدب  مماس باشند. در این مقاله کارهای قبلی برای چندخطی‌ها توسعه داده شده است. عملا به‌جای جداسازی نقاط، جداسازی چندخطی‌ها مدنظر ما است. کاربرد مهم جداسازی چندخطی‌ها در کلاس‌بندی اشیایی که به‌جای نقطه با پاره خط یا چندضلعی توصیف ‌می‌شوند، مطرح می‌شود. زمان اجرای الگوریتم ما  O(N^2*logN) است که N=n+m و n تعداد خطوط آبی در مجموعه P و m تعداد خطوط قرمز در مجموعه Q است.
کلیدواژه‌ها
موضوعات

[1] Cristianini, N. & Taylor, J.S. (2000). An introduction to support vector machines and other kernel-based learning methods, Cambridge University Press.
[2] Dobkin., D.P., Gunopulos, D. & Maass, W. (1996). Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning, Journal of Computer and System sciences, 52(3), 453-470.
[3] Duda, R.O., Hart, P.E. & Stork, D.G. (2012). Pattern classification, John Wiley & Sons.
[4] J. Eckstein, P.L., Hammer, Y., Liu, M., Nediak, B. & Simeone, (2002). The maximum box problem and its application to data analysis, Computational Optimization and Applications, 23(3), 285-298.
[5] Edmonds, J., Gryz, J., Liang, D.L. & Miller, R.J. (2003). Mining for empty spaces in large data sets. Theoretical Computer Science, 296(3) 435-452.
[6] Megiddo, N. (1983). Linear-time algorithms for linear programming in and related problems, SIAM J. Comput, 12(4) p. 759.
[7] O’Rourke, J., Kosaraju, S.R., & Megiddo, N. (1986). Computing circular separability, Discr. Comput, Geom, 1(1) p. 105.
[8] Edelsbrunner, H. & Preparata, F.P. (1988). Minimum polygonal separation, Inform. Comput. 77  P. 218.
[9] Fekete, S. (1992). On the complexity of min-link red-blue separation, Manuscript.
[10] Mitchell, J.S.B. (1993). Approximation algorithms for geometric separation problems, Technical Report, State University of New York at Stony Brook.
[11] Moslehi, Z. & Bagheri, A.B. (2016). Separating bichoromatic point sets by disjoint isothetic rectangles, Scientia Iranica. Transaction D, Computer Science & Engineering, Electrical, 23(3) pp. 1228.
[12] Acharyya, A., Minati, De., Nandy, S.C. & Pandit, S. (2020). Variations of largest rectangle recognition amidst a bichromatic point set, Discrete Applied Mathematics, 286 pp.35-50.
[13] Moslehi, Z., & Bagheri, A.B. (2017). Separating bichromatic Point Sets by Minimal Triangles, International Journal of Foundations of Computer Science, 28(4) p.309.
[14] Sheikhi, F., Mohades, A., Berg, B., & Mehrabi, A.D. (2017). Separability of imprecise points, Computational Geometry 61, 24-37.
[15] Bandyapadhyay, S. & Banik, A. (2017). Polynomial time algorithms for bichromatic problems, In 553 Conference on Algorithms and Discrete Applied Mathematics, Springer, 12–23.
[16] Har-Peled, S. & Jones, M. (2018). On separating points by lines, SODA '18: Symposium on Discrete Algorithms New Orleans Louisiana January, 918–932.
[17] Xue, J., Li, Y. & Janardan, R. (2018). On the separability of stochastic geometric objects, with applications, Computational Geometry Volume 74,  1-20.
[18] Bonnet, E. & Lampis, M. (2019). On the Parameterized Complexity of Red-Blue Points Separation, Journal of Computational Geometry, 10(1) 181-206.
[19]  Kreveld, M., Lankveld, T. & Veltkamp, R. (2011) Identifying well-covered minimal bounding rectangles in 2D point data, Computers & Graphics, 35- 719-725.
[20] Toussaint, G. (1983). Solving geometric problems with the rotating calipers, In Proc. of the IEEE MELECON '83, A10.02/1-4.
[21] Moghaddam, M.H. & Bagheri, A.R. (2022). Separating bichromatic polylines by fixed-angle minimal triangles, Volume 29, Issue 5, September and October 2022, Pages 2405-2417.