Comment by Animats

The main precomputation needed is the result from the previous frame. Algorithms of this type of convex hull distance are really cheap, because you don't need to examine every vertex, just trace a path to the closest points. That's roughly O(sqrt(n)). If you're doing this over and over as objects move, and start from the previous result, it approaches O(1).