Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6868491 | Computational Geometry | 2018 | 20 Pages |
Abstract
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 a homothet of S having the two points on its boundary and whose interior is empty of points of P. A matching in GS(P) is said to be strong, if the homothets of S representing the edges of the matching are pairwise disjoint, i.e., they 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 that computes a strong matching in GS(P); if S is a diametral-disk, then it computes a strong matching of size at least ânâ117â, and if S is an equilateral-triangle, then it computes a strong matching of size at least ânâ19â. If S can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least ânâ14â in GS(P). When S is an axis-aligned square, we compute a strong matching of size at least ânâ14â in GS(P), that improves the previous lower bound of ân5â.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ahmad Biniaz, Anil Maheshwari, Michiel Smid,