EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) like roating caliphers!
If you compute all the distances between all the sides the complexity is of the order $n^2$. In 2D there is the rotating caliphers method that apparently solves the problem in $O(n)$(?) time. Isn't the general case also formulatable as a quadratic programming problem? Does that show that it is solvable in time linear in $n$ (since quadratic programming is so close to linear programming which is solvable in time linear to the number of inequalities if the dimension is fixed).