In case you're still interested in an exact solution, I think computing the Voronoi diagram for the polygon (treating each vertex as a point) should help in fin

In case you're still interested in an exact solution, I think computing the Voronoi diagram for the polygon (treating each vertex as a point) should help in finding the answer. The deepest point should lie on one of the edges of the Voronoi diagram.