Strong Matching of colored points with Geometric Shapes

Let P be a point set in the plane such that each of its elements is coloredeither red or blue. Given a convex geometric shape , a geometric graph Gs(P) onP is defined to have an edge between two points if and only if there exists ahomothet of S having the two points on its boundary and whose interior is emptyof points of P. A matching in Gs(P)is said to be strong, if the homothets of Srepresenting the edges of the matching are pairwise disjoint, i.e., they do not shareany point in the plane. Such a matching is monochromatic if every convexgeometric shape contains points of the same color, and is bichromatic if everyconvex geometric shape contains points of different colors. We consider theproblem of computing a strong matching in Gs(P), where S is a diametral disk, anequilateral triangle, or a square.In this paper we study the following two problems:۱. Find a Maximum Monochromatic Matching of S with convex geometricShapes. (MMMS)۲. Find a Maximum Bichromatic Matching of S with convex geometricShapes. (MBMS)

کلیدواژه ها:

Monochromatic Matching ، Bichromatic Matching ، Strong Matching