Fixed-orientation equilateral triangle matching of point sets
Given a point set P and a class C of geometric objects, GC(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∈C containing both p and q but no other points from P. We study G▿(P) graphs where ▿ is the class of downward equilateral triangles (i.e., 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-Θ6 graphs and TD-Delaunay graphs.The main result in our paper is that for point sets P in general position, G▿(P) always contains a matching of size at least ⌈|P|-13⌉ and this bound is tight. We also give some structural properties of G[U+2721](P) graphs, where [U+2721] 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[U+2721](P) is simply a path. Through the equivalence of G[U+2721](P) graphs with Θ6 graphs, we also derive that any Θ6 graph can have at most 5n-11 edges, for point sets in general position.
|Keywords||Delaunay graphs, Geometric graphs, Half-Θ6 graphs, Matching|
|Journal||Theoretical Computer Science|
Babu, J. (Jasine), Biniaz, A. (Ahmad), Maheshwari, A, & Smid, M. (2014). Fixed-orientation equilateral triangle matching of point sets. Theoretical Computer Science, 555(C), 55–70. doi:10.1016/j.tcs.2013.11.031