It is well known that a planar triangulation has a linear size. This result is due to the Euler characteristic. In dimension 3 or higher, we can find triangulations that have a size of $\Theta(n^2)$.

We compute the size of the triangulation when the points are distributed on surface. For instance, on a cylinder, it is proved that you can have a bad size, $O(n\sqrt n)$, even with a good deterministic sample. But if the points are distributed at random, then a tight bound $\Theta(n \ln n)$ is reached in expectation.

We try to adapt those results on generic surfaces where good samples lead to a triangulation in $O(n \ln n)$, and where we expect a linear expected size.