A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation (Q2489546)

The dilatation of a plane graph \(G\) is the maximum value of the ratio between the length of a shortest path between two points \(p\) and \(q\) in \(G\) and the Euclidean distance \(d(p,q)\) taken over all pairs of points \(p\) and \(q\) in \(G\). The authors design a fully polynomial-time approximation scheme for the problem of finding a triangulation of a simple polygon with a constant number of sources of dilation that achieves the minimum vertex dilation. Some open problems are formulated.