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.

  • 1
    $\begingroup$ 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. $\endgroup$ – orlp Sep 26 '16 at 20:21
  • $\begingroup$ Good catch! I forgot to mention that I do not allow Steiner points in my triangulations. I will update the question. $\endgroup$ – Nizbel99 Sep 26 '16 at 23:07
  • $\begingroup$ Interesting question, but I am curious what application this may have. Can you tell? $\endgroup$ – Discrete lizard Feb 2 '17 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)

Example polygon

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.


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.