Strong matching of points with geometric shapes

DOI10.1016/J.COMGEO.2017.06.009MaRDI QIDQ1699290zbMATH OpenOpenAlexFDO

Authors Ahmad Biniaz, Anil Maheshwari, Michiel Smid

Publication date 19 February 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04871

zbMATH Keywords

geometric graphsmaximum matchingstrong matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 $lceilfracn-117ceil$, and if $S$ is an equilateral-triangle, then it computes a strong matching of size at least $lceilfracn-19ceil$. If $S$ can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least $lceilfracn-14ceil$ in $G_S(P)$. When $S$ is an axis-aligned square we compute a strong matching of size $lceilfracn-14ceil$ in $G_S(P)$, which improves the previous lower bound of $lceilfracn5ceil$.

Recommendations

• Matching points with rectangles and squares
• Fixed-orientation equilateral triangle matching of point sets
• Matching Points with Circles and Squares
• SOFSEM 2006: Theory and Practice of Computer Science
• Matching points with squares

Cites work

• Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
• Fixed-orientation equilateral triangle matching of point sets
• Geometrical Extrema Suggested by a Lemma of Besicovitch
• Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
• Matching Points with Circles and Squares
• Matching points with rectangles and squares
• Matching points with squares
• Matchings in higher-order Gabriel graphs
• On the stretch factor of convex Delaunay graphs
• There are planar graphs almost as good as the complete graph
• Toughness and Delaunay triangulations
• Transitions in geometric minimum spanning trees

Cited in

(6)

• Matching points with disks with a common intersection
• Fixed-orientation equilateral triangle matching of point sets
• scientific article; zbMATH DE number 2200862 (Why is no real title available?)
• Matching Points with Circles and Squares
• Fixed-orientation equilateral triangle matching of point sets
• Matching points with rectangles and squares

This page was built for publication: Strong matching of points with geometric shapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699290)