Finding The Maximum Monochromatic Polygon

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 On2lognm 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.