# Convex triangulations

Given a set of $$n$$ points in the Euclidean plane of which no three are collinear, does there always exist a convex triangulation and how can one be found algorithmically?

In this context a convex triangulation shall mean a triangulation in which the union of triangles with a common corner-point inside the convex hull constitute to a convex polygon. Point $$4$$'s star is reflex at $$3$$, Point $$3$$'s star is reflex at $$4$$.
Here's an argument that those are the only two triangulations. Each interior point ($$3$$ and $$4$$) must be degree-$$3$$ or degree-$$4$$: degree-$$3$$ to span more than $$180^\circ$$, and at most degree-$$4$$ because there are only four other points. In the left figure point $$3$$ has degree-$$3$$ and point $$4$$ degree-$$4$$, and in the right figure point $$3$$ has degree-$$4$$ and point $$4$$ degree-$$3$$. There must be a total of $$9$$ edges, $$6$$ of them diagonals. Then the diagonals in the two figures are forced.
• Observation: If all neighbors of an interior vertex $v$ in a convex triangulation are interior vertices, then the degree of $v$ is at least $5$. – Jan Kyncl Feb 22 at 11:25
• When looking at the figure, I noticed that around a vertex of degree at most $4$, two of the consecutive angles will sum up to more than 180 degrees. So the neighbor along the edge common to those two angles will have a nonconvex union of incident triangles. – Jan Kyncl Feb 22 at 14:18