
arXiv: 1503.04871
Let $P$ be a set of $n$ points in general position in the plane. Given a convex geometric shape $S$, a geometric graph $G_S(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_S(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_S(P)$, where $S$ is a diametral-disk, an equilateral-triangle, or a square. We present an algorithm which computes a strong matching in $G_S(P)$; if $S$ is a diametral-disk, then it computes a strong matching of size at least $\lceil \frac{n-1}{17} \rceil$, and if $S$ is an equilateral-triangle, then it computes a strong matching of size at least $\lceil \frac{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 \frac{n-1}{4} \rceil$ in $G_S(P)$. When $S$ is an axis-aligned square we compute a strong matching of size $\lceil \frac{n-1}{4} \rceil$ in $G_S(P)$, which improves the previous lower bound of $\lceil \frac{n}{5} \rceil$.
Computational Geometry (cs.CG), FOS: Computer and information sciences, Extremal problems in graph theory, maximum matching, Discrete Mathematics (cs.DM), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), geometric graphs, Computer Science - Computational Geometry, strong matching, Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, Extremal problems in graph theory, maximum matching, Discrete Mathematics (cs.DM), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), geometric graphs, Computer Science - Computational Geometry, strong matching, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
