# Fixed-Orientation Equilateral Triangle Matching of Point Sets

Given a point set $P$ and a class $\mathcal{C}$ of geometric objects, $G \mathcal{C}(P)$ is a geometric graph with vertex set $P$ such that any two vertices $p$ and $q$ are adjacent if and only if there is some $C \in \mathcal{C}$ containing both $p$ and $q$ but no other points from $P$. We study $G {\bigtriangledown}(P)$ graphs where $\bigtriangledown$ is the class of downward equilateral triangles (ie. equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-$\Theta 6$ graphs and TD-Delaunay graphs. The main result in our paper is that for point sets $P$ in general position, $G {\bigtriangledown}(P)$ always contains a matching of size at least $\lceil\frac{n-2}{3} ceil$ and this bound cannot be improved above $\lceil\frac{n-1}{3} ceil$. We also give some structural properties of $G {\davidsstar}(P)$ graphs, where $\davidsstar$ is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of $G {\davidsstar}(P)$ is simply a path. Through the equivalence of $G {\davidsstar}(P)$ graphs with $\Theta 6$ graphs, we also derive that any $\Theta 6$ graph can have at most $5n-11$ edges, for point sets in general position.

Author: Jasine Babu; Ahmad Biniaz; Anil Maheshwari; Michiel Smid

Source: https://archive.org/