Geometric objects covering all red points and minimum blue points

Year 2025, Volume: 9 Issue: 1, 47 - 55, 20.01.2025

Sukanya Maji , Sanjib Sadhu

https://doi.org/10.31127/tuje.1481901

Abstract

Inspired by the applications in machine learning, we study a variation of the separation problem for a given set of bichromatic points- blue (B) and red (R) with |B|=m and |R|=n, where these sets are separated by a geometric object. The objective of our work is to compute one or two geometric covering objects whose union covers every red point and as few blue points as possible. We consider rectangles, squares and convex polygons as the geometric covering object for the bichromatic point set. We design an O(m+n) time algorithm to solve the aforesaid problem using two disjoint rectangles. For the same problem, it takes O(m) time to compute a square which is used as geometric covering object. We also present an algorithm for the same problem with two disjoint squares as the geometric covering objects in O(nm) time. If the geometric covering objects are two disjoint convex polygons, then it takes O(n^2 (m+n)logn) time. The preprocessing tasks in the algorithms for each of the aforesaid problems need O(mlogm+nlogn) time and all these problems need O(m+n) space.

Keywords

Bichromatic point sets, Separator of point sets, Geometric Covering, Line sweeping, Algorithm

References

• Acı, M., Acı, Ç. İ., & Avcı, M. (2018). Performance comparison of anfis, ann, svr, cart and mlr techniques for geometry optimization of carbon nanotubes using castep. Turkish Journal of Engineering, 2(3), 119-124.
• Dennison, R., Dasebenezer, G. K., & Dennison, R. (2024). Cervic cancer classification using quantum fuzzy set. Turkish Journal of Engineering, 8(4), 687-694
• Aydin, O. F., & Gökaşar, İ. (2021). The effects of including social factors in ride-matching algorithms on the performance and the quality of matches. Turkish Journal of Engineering, 5(1), 41-47.
• Juraev, D. A., & Bozorov, M. N. (2024). The role of algebra and its application in modern sciences. Engineering Applications, 3(1), 59-67.
• Kreveld, M. V., Lankveld, T. V., & Rie, M.D. (2012). (α, δ)-Sleeves for reconstruction of rectilinear building facets. In Progress and New Trends in 3D Geoinformation Sciences. Springer Berlin Heidelberg, 231-247.
• Kreveld, M.V., Lankveld, T.V., & Veltkamp, R. (2009). Identfying well-covered minimal bounding rectangles in 2D point data. In 25th European Workshop on Computational Geometry (EuroCG), 277-280.
• Lankveld, T.V., Kreveld, M.V., & Veltkamp, R. (2011). Identifying rectangles in laser range data for urban scene reconstruction. Computers & Graphics, 35(3), 719-725.
• Maji, S., Pandit, S., & Sadhu, S. (2024). Generalized Red-Blue Circular Annulus Cover Problem. CoRR abs/2402.13767.
• Maji, S., Pandit, S., & Sadhu, S. (2023). Red-Blue Rectangular Annulus Cover Problem. In International Workshop on Frontiers in Algorithmics (IJTCS-FAW), 195-211.
• Shanjani, S.H. (2020). Hardness of approximation for red-blue covering. In: Canadian Conference on Computational Geometry (CCCG), 39–48.
• Preparata, F. P., & Shamos, M. I. (2012). Computational Geometry: An Introduction. Springer Science & Business Media.
• de Berg, M., Kreveld, M.V., Overmars, M., Schwarzkopf, O. (2000). Computational Geometry: Algorithms and Applications. Springer Science & Business Media.
• Megiddo, N. (1983). Linear-time algorithms for linear programming in R^3 and related problems. SIAM journal on computing, 12(4), 759-776.
• O'Rourke, J., Kosaraju, S.R., & Megiddo, N. (1986). Computing circular separability. Discrete & Computational Geometry, 1, 105-113.
• Edelsbrunner, H., & Preparata, F.P. (1988). Mini-mum polygonal separation. Information and Compu-tation, 77, 218-232.
• Fekete, S. (1992). On the complexity of min-link red-blue separation. Manuscript, department of applied mathematics, SUNY Stony Brook, NY.
• Mitchell, J.S.B. (1993). Approximation algorithms for geometric separation problems. In Technical report. State University of New York at Stony Brook
• Seara, C. (2002). On geometric separability. Applied Mathematics, Ph. D. Thesis, University of. Polit'ecnica de Catalunya.
• Hurtado, F., Noy, M., Ramos, P. A., & Seara, C. (2001). Separating objects in the plane by wedges and strips. Discrete Applied Mathematics, 109(1-2), 109-138.
• Barbay, J., Chan, T.M., Navarro, G., & P ́erez-Lantero, P. (2014). Maximum-weight planar boxes in O(n2) time (and better). Information Processing Letters. 114(8), 437–445.
• 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.
• Eckstein, J., Hammer, P.L., Liu, Y., Nediak, M., & Simeone, B. (2002). The maximum box problem and its application to data analysis. Computational Optimization and Applications. 23(3), 285–298.
• Liu, Y., & Nediak, M. (2003). Planar case of the maxium box and related problems. In: Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG), Halifax, Canada, 14–18.
• Backer, J., & Keil, J.M. (2010). The mono- and bichromatic empty rectangle and square problems in all dimensions. In: LATIN 2010: Theoretical Informatics, 9th Latin American Symposium (LATIN), Proceedings,14–25.
• Bereg, S., Daescu, O., Zivanic, M., & Rozario, T. (2015). Smallest maximum-weight circle for weighted points in the plane. In: Computational Science and Its Applications (ICCSA) - 15th International Conference, Proceedings, 244–253.
• Abidha, V.P., & Ashok, P. (2022). Geometric separability using orthogonal objects. Information Processing Letters 176, 106245.
• Carr, R.D., Doddi, S., Konjevod, G., & Marathe, M. (1999). On the red-blue set cover problem. Technical report, Sandia National Lab (SNL-NM), Albuquerque, NM (United States), Sandia, 345-353.
• Chan, T.M., & Hu, N. (2015). Geometric red–blue set cover for unit squares and related problems. Computational Geometry. 48(5), 380–385.
• Madireddy, R.R., Nandy, S.C., & Pandit, S. (2021). On the geometric red-blue set cover problem. International Workshop on Algorithms and Computation (WALCOM), 129–141, Springer
• Abidha, V., & Ashok, P. (2024). Red blue set cover problem on axis-parallel hyperplanes and other objects. Information Processing Letters. 186, 106485.
• Bereg, S., Cabello, S., Díaz-Báñez, J.M., Pérez-Lantero, P., Seara, C., & Ventura, I. (2012). The class cover problem with boxes. Computational Geometry 45(7), 294–304.
• Bitner, S., Cheung, Y., & Daescu, O. (2010). Minimum separating circle for bichromatic points in the plane. In 2010 International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), 50-55. IEEE.