Fast Polygonal Distance Approximation?

Question

I have a large number of polygons, and I'd like to calculate an approximation of the distance from each one to each other one.

However, calculating the distance between two polygons is slow. Meanwhile, approximating each polygon as its centroid and then calculating distance is very fast, but not so accurate. What approximation of a polygon can I use so that I can obtain both quick and (reasonably) accurate distances?

Answer 1

Although this doesn't quite answer the question as asked, what worked for me was to use the centroid distance if the shapes were far away and use the more precise polygon distance when they were closer.