# What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

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).

-
Essentially the same algorithm works in 3 dimensions. Prof O'Rourke will hopefully come by with some useful references. Be careful about assuming quadratic programming is always close to linear programming. It is easy to get non convex problems that seem like they should be convex (a quadratic objective with linear constraints is not necessarily convex.) I don't think that this is a problem here, but quadratic programming to find the minimum distance is swatting flies with a sledgehammer. –  deinst Feb 7 '12 at 16:03
I'm aware that the objective function given as a quadratic form needs a positive definit matrix so that the quadratic programm is efficiently solvable - otherwise the general case is np-hard. –  Peter Sheldrick Feb 7 '12 at 21:05

Just found an excellent article as a link to the LP-type problem Wikipedia page (mostly written by David Eppstein) authored by the august trio of Matoušek, Sharir & Welzl.

Not only is this problem a so called LP-type one (like for example finding the minimum enclosing ellipsoid of a set of points) but it is also solvable in linear time in $\mathbb{R}^3$!.

Just look at page 15 of the linked article, there you find the running time of

$$\min \{2^{d+\mathcal O(\sqrt d)} n, \textrm{doesn't matter}\}$$

which when inserting $d=3$ yields $\min \{2^{3+\mathcal O(\sqrt 3)} n=n,...\}=\mathcal O(n)$.

Hence this question is answered in the affirmative.

-