2015/03/16 by Ahmad Biniaz, Biniaz, Ahmad, Anil Maheshwari +3 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.1503.04871
arxiv created 2015/03/16 · arxiv updated 2015/03/18
Let P be a set of n points in general position in the plane. Given a convex geometric shape S, a geometric graph GS(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 GS(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 GS(P), where S is a diametral-disk, an equilateral-triangle, or a square. We present an algorithm which computes a strong matching in GS(P); if S is a diametral-disk, then it computes a strong matching of size at least \lceil (n-1)/(17) \rceil, and if S is an equilateral-triangle, then it computes a strong matching of size at least \lceil (n-1)/(9) \rceil. If S can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least \lceil (n-1)/(4) \rceil in GS(P). When S is an axis-aligned square we compute a strong matching of size \lceil (n-1)/(4) \rceil in GS(P), which improves the previous lower bound of \lceil (n)/(5) \rceil.