2018-03-01

# Strong matching of points with geometric shapes

## Publication

### Publication

*
Computational Geometry
,
Volume 68
p. 186-
205
*

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 ⌈[Formula presented]⌉, and if S is an equilateral-triangle, then it computes a strong matching of size at least ⌈[Formula presented]⌉. If S can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least ⌈[Formula presented]⌉ in GS(P). When S is an axis-aligned square, we compute a strong matching of size at least ⌈[Formula presented]⌉ in GS(P), that improves the previous lower bound of ⌈[Formula presented]⌉.

Additional Metadata | |
---|---|

Geometric graphs, Maximum matching, Strong matching | |

dx.doi.org/10.1016/j.comgeo.2017.06.009 | |

Computational Geometry | |

Organisation | Computational Geometry Lab |

Biniaz, A. (Ahmad), Maheshwari, A, & Smid, M. (2018). Strong matching of points with geometric shapes.
Computational Geometry, 68, 186–205. doi:10.1016/j.comgeo.2017.06.009 |