Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.