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 AS, and an affine invariant triangulation, denoted DTAS [S]. We revisit the AS-norm from a geometric perspective, and show that DTAS [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. In addition, we provide different affine invariant order methods of a point set S and of the vertices of a polygon P that can be combined with well-known algorithms in order to obtain other affine invariant triangulation methods of S and P.

31st Canadian Conference on Computational Geometry, CCCG 2019
School of Computer Science

Bose, P, Cano, P. (Pilar), & Silveira, R.I. (Rodrigo I.). (2019). Affine invariant triangulations. In Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019 (pp. 250–256).