Triangulating Regular Polygons to Minimize Dilation


The dilation between two points of a Euclidean graph is defined as the ratio of the length of the shortest path between the points and the Euclidean distance between the points. The dilation of a graph is defined as the maximum over all vertex pairs (x,y) of the dilation between x and y.

We consider triangulations of regular polygons. Given a regular n-gon, what is the triangulation that minimizes the dilation? Can we find a good upper bound for the dilation? A good lower bound?

The trivial upper bound for dilation is pi/2. This is achieved without any triangulation. We can do slightly better and show that, if the triangulation is a fan (i.e. every edge of the triangulation starts from the same vertex), the dilation will be at most approximately 1.48454 (proof to appear).

Building a slightly more complex triangulation, we can prove a better upper bound of about 1.45595 if n is divisible by 6 (proof to appear). We call this triangulation the 6-fan and it is constructed as follows:

  1. Inscribe an equilateral triangle in the n-gon, with vertices touching vertices.
  2. For each other vertex v of the n-gon, draw an edge from v to the closest vertex of the inscribed equilateral triangle.

The dilation of the 6-fan approaches 1.45595 as n approaches infinity. Is the 6-fan optimal as n approaches infinity? Or can we do better?