I'm a little confused, because I thought, there would be C(n-2) triangulations, where C(n) is the n-th catalan number and n the amount of points in the set. But it turns out, that there seems to be sets with less possible triangulations, as not every vertex can be flipped in any case. So is C(n-2) just the upper limit? Or is this really just applicable for sets, where all points lie on the convex hull, like Euler was originally writing it?
Edit: So is there a formula for the upper limit of the triangulations of a set of points in 2d?
Thank you in advance.
The short answer is that we do not know for sure what the minimum for $n$ points in general position is (when the points are not in general position then the minimum is 1 for every $n$). The Catalan number $C_{n-2}$ is the exact number of triangulations $n$ points in convex position in the plane admit, but it is neither the maximum nor the minimum when points are not required to be in convex position.
The conjectured minimum configuration is the double circle on $n$ points, yielding about $(\sqrt{12})^{n} \approx (3.46..)^n$ triangulations, up to a polynomial factor. The Catalan numbers grow as $4^n$ up to a polynomial factor, so the double circle has way fewer (exponentially fewer) triangulations than points in convex position.
The best lower bound for the number of triangulations a set of $n$ points in general position must have is currently $\Omega(2.631^n)$ by Aichholzer et al [1]. They also show (by a large computer case analysis) that the double circle is indeed the minimal configuration for up to $n=15$ points (for more than $15$ points it is still unknown).
As for maximal configurations, I do not think there is even a precise conjecture (for a time it was thought that the maximum is about $8^n$ but this is no longer the case). The point configuration yielding the (asymtotically) maximum number of triangulations currently known is a sort of generalized double chain constructed by Dumitrescu et al. [2]. They show it has at least $\Omega(8.65^n)$ triangulations. The best upper bound on the number of triangulations of $n$ points in the plane is $30^n$ in [3], which comes from an improved analysis on an earlier proof by Sharir and Welzl. No doubt the true maximum is closer to $8.65^n$ than $30^n$
[1] Aichholzer et al., An improved lower bound on the minimum number of triangulations, SoCG 2016.
[2] Dumitrescu et al., Bounds on the Maximum Multiplicity of Some Common Geometric Graphs, SIAM Journal on Discrete Mathematics, 2013.
[3] Sharir and Sheffer, Counting Triangulations of Planar Point Sets , The Electronic Journal of Combinatorics, 2011.