  We study affine invariant 2D triangulation methods. That is, methods that
produce the same triangulation for a point set $S$ for any (unknown) affine
transformation of $S$. Our work is based on a method by Nielson [A
characterization of an affine invariant triangulation. Geom. Mod, 191-210.
Springer, 1993] that uses the inverse of the covariance matrix of $S$ to define
an affine invariant norm, denoted $A_{S}$, and an affine invariant
triangulation, denoted ${DT}_{A_{S}}[S]$. We revisit the $A_{S}$-norm from a
geometric perspective, and show that ${DT}_{A_{S}}[S]$ can be seen as a
standard Delaunay triangulation of a transformed point set based on $S$. We
prove that it retains all of its well-known properties such as being 1-tough,
containing a perfect matching, and being a constant spanner of the complete
geometric graph of $S$. We show that the $A_{S}$-norm extends to a hierarchy of
related geometric structures such as the minimum spanning tree, nearest
neighbor graph, Gabriel graph, relative neighborhood graph, and higher order
versions of these graphs. In addition, we provide different affine invariant
sorting methods of a point set $S$ and of the vertices of a polygon $P$ that
can be combined with known algorithms to obtain other affine invariant
triangulation methods of $S$ and of $P$.
