Strong Matching of Points with Geometric Shapes

الأصل · EN

Let P be a set of n points in general position in the plane. Given a convex geometric shape S, a geometric graph Gₛ(P) on P is defined to have an edge between two points if and only if there exists an empty homothet of S having the two points on its boundary. A matching in Gₛ(P) is said to be strong, if the homothests of S representing the edges of the matching, are pairwise disjoint, i.e., do not share any point in the plane. We consider the problem of computing a strong matching in Gₛ(P), where S is a diametral-disk, an equilateral-triangle, or a square. We present an algorithm which computes a strong matching in Gₛ(P); if S is a diametral-disk, then it computes a strong matching of size at least n-1/17, and if S is an equilateral-triangle, then it computes a strong matching of size at least n-1/9. If S can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least n-1/4 in Gₛ(P). When S is an axis-aligned square we compute a strong matching of size n-1/4 in Gₛ(P), which improves the previous lower bound of n/5.