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.


Nice idea but it seems not to always exist:

          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.

  • 4
    $\begingroup$ It is an interesting question: When does a convex triangulation exist? And what is the computational complexity to decide if a set of points admits a convex triangulation? $\endgroup$ – Joseph O'Rourke Feb 22 at 0:02
  • 2
    $\begingroup$ 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$. $\endgroup$ – Jan Kyncl Feb 22 at 11:25
  • $\begingroup$ @JanKyncl: May I ask how you arrived at this interesting fact? $\endgroup$ – Joseph O'Rourke Feb 22 at 12:56
  • 2
    $\begingroup$ 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. $\endgroup$ – Jan Kyncl Feb 22 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.