3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Nice idea but it seems not to always exist:

          ConvexTriangulation
          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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Feb 22, 2020 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
    Commented Feb 22, 2020 at 11:25
  • $\begingroup$ @JanKyncl: May I ask how you arrived at this interesting fact? $\endgroup$
    – Joseph O'Rourke
    Commented Feb 22, 2020 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
    Commented Feb 22, 2020 at 14:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .