# Unique triangulation duals of simple polygons

Given a triangulation (without Steiner points) of a simple polygon $P$, one can consider the dual of this triangulation, which is defined as follows. We create a vertex for every triangle in our triangulation, and we connect two vertices if the corresponding triangles share an edge. The dual graph is known to be a tree with maximum degree three.

For my application, I am interested in the following. Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$. Here, the triangulation of $P$ may not be unique, but I require that the dual graph be unique.

This is certainly true when $T$ is a path, but becomes unclear when you have vertices of degree three.

• The dual graph is not necessarily a tree. Consider this star-like shape, which depending on your definition of sharing an edge (full or partial) is either a disjoint graph of 4 vertices, or a 4-cycle.
– orlp
Sep 26, 2016 at 20:21
• Good catch! I forgot to mention that I do not allow Steiner points in my triangulations. I will update the question. Sep 26, 2016 at 23:07
• Interesting question, but I am curious what application this may have. Can you tell? Feb 2, 2017 at 22:05

Given a tree $T$ with maximum degree three, is there always a simple polygon $P$ such that the dual of every triangulation (without Steiner points) of $P$ is equal to $T$?

Yes. To show this, I will give a procedure to get the seemingly slightly stronger result*:

Given a tree $T$ with maximum degree three, construct a simple polygon $P$, such that the unique triangulation of $P$ (without Steiner points) has $T$ as its dual.

Start by creating an initial triangle $\Delta_0$, representing some vertex $v_0$ in $T$ and add $v_0$ to the queue $Q$. Then, repeat the following until $Q$ is empty:

• Pop the top element, $v$, from the queue.
• For each neighboring vertex $w$ that for which we have not placed a triangle yet, choose a side $AB$ of triangle $\Delta_v$ and a point $D$ inside the conical regions generated by the line through $AB$ and its neighboring segments, such that the triangle $\Delta ABD$ does not intersect any other triangles. (See figure below) Set $\Delta_w\leftarrow\Delta ABD$ and add $w$ to $Q$. This image gives an example of a possible polygon $P$ (left) for the given $T$ (right) To see why this procedure works, first note that after creating a new triangle, the segments $AB$ and $AD$ generate a cone that has a non-empty region not-intersecting with the existing triangles (see also the earlier figure), so we can find a suitable point at every step and create a polygon.

Second, we have chosen the triangles such that line segment between $CD$ does not completely lie inside $P$. If there exists a corner-point $Q \notin \{B,D\}$ of the already placed triangles such that $DQ$ is fully in $P$, then it must lie inside the cones generated by $AD$ and $BD$. However, since the part of this cone that does not lie inside $\Delta ABD$ is contained in the cone generated by the earlier placed triangle, such a $Q$ exists only if there exists an analogous point for the earlier placed triangle. Since there does not exist such a point for the first triangle, this means there is no such point for any triangle we add.

This means that all pairs $(X,Y)$ of any corner point of $P$ for which the segment $XY$ is fully contained in $P$ is already in the constructed triangulation, so the triangulation is unique for $P$ (all triangulations add the same number of internal segments)

Note that the polygons constructed in this method tend to have rather sharp angles. I suspect arbitrary large graphs require polygons with arbitrary small angles, which could be a problem when drawing these polygons with finite precision.

*: The difference is that, if we interpret 'unique' as up to isomorphism (which is consistent with uniqueness of triangulations and duals being different), we would be ok with a polygon having multiple triangulations that all have isomorphic duals. However, it is possible to 'attach' more triangles to those polygons to ensure some duals are no longer isomorphic.