Finding The Maximum Monochromatic Polygon
Sara Khalafi, Alireza Bagheri, Mohammad Mansoor Riahi Kashani
Index Terms— Computational Geometry, Genetic Algorithm, Colored Points Coverage, Separation, Polygon Triangulation
Abstract— Covering the set of points with a geometric shape is an important problem in computational geometry. In this problem, given a set of points in the plane of total size n and a geometric shape, covering the points with the geometric shape with minimum perimeter or area is the goal. The points may have different colors or divided into desirable and non-desirable points. On the other hand, in the separability problem, it is required that all of the desirable points lay inside the geometric shape and all of the other lay outside it. There has been a fair amount of work on different kinds of separators such as rectangles, squares, circles, etc. In this paper, a new algorithm based on genetic algorithm is presented for finding the maximum monochromatic polygon, which contains the maximum number of desirable points while avoids non-desirable points. Finding the maximum monochromatic polygon is an important problem in computational geometry which has many applications in different fields. Also, another algorithm is introduced based on triangulation of blue points, which has O(n2(logn+m)) time, where n represents the number of blue points and m represents the number of red points. Both algorithms are evaluated and compared to optimal solutions. Both algorithms are near-optimal, i.e. their solutions are close to optimal solutions, but they are not necessarily optimal. Of course, in some cases they yield optimal solutions.
 D. P. Dobkin, D. Gunopulos, “Computing the maximum bichromatic discrepancy with applications to computer graphics and machine learning,” Journal of Computer and System Sciences 52, pp. 453–470 , 1996.
 J. C. Burges, "A Tutorial on Support Vector Machines for Pattern Recognition," Kluwer Academic Publishers Hingham, vol. 2, no. 2, pp. 121-167, June 1998
 P. Fischer, "Sequential and parallel algorithms for finding a maximum convex polygon," Elsevier, Computational Geometry: Theory and Applications, vol. 7, no. 3, pp. 187-200, 1997.
 C. Bautista-Santiago, J. M. DíAz-BáñEz, D. Lara, P. PéRez-Lantero, P. Urrutia and I. Ventura, "Computing optimal islands," Elsevier , Operations Research Letters, vol. 39, no. 4, pp. 246-251, 2011.
 D. Goldberg, K. Sastry and G. Kendall, “Genetic Algorithms,” Search Methodologies, pp 97-125 , 2001