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:
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?