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.

Given: a set $S$ of points in $\mathbb{R}^3$.

Find: the smallest oriented bounding box that contains all the points. Note, the bounding box is "oriented" and thus need not be axis-aligned.

Can this be formulated as an optimization problem? Preferably a convex optimization problem!

The optimal box should be smallest by either volume or perimeter (whichever is easier, but ideally, both solutions will be presented).

I hope the optimization problem is simpler to code than Joseph O'Rourke's Minimum Enclosing Box Algorithm (pdf) and can be solved using a standard optimization package.

For example, the smallest enclosing hypersphere containing a set of points $S$ can be defined by a center $c$ and radius $r$. It is the solution to the problem:

$$\textrm{minimize}_{c,r} \; r^2 \;\;$$ $$ \textrm{subject to: } \; \left| \left| c - s \right| \right|^2 \leq r^2 \; \forall s \in S$$

I'm asking for a similar formulation for an oriented bounding box instead of a hypersphere, if possible.

share|improve this question
3  
Are you asking to solve the same problem as in my paper you cite, but just by a different method? Hopefully using off-the-shelf optimization code? Or are you asking to solve a different problem? –  Joseph O'Rourke Mar 20 '11 at 0:53
    
I am asking to solve the exact same problem you address in your paper. I am asking how to formulate the problem in standard optimization form: "minimize f(x) subject to g(x) <= 0", so that I can solve it using off-the-shelf optimization code. I hope this formulation is simpler to code than the rotating calipers algorithm in the paper. –  dsg Mar 20 '11 at 1:54
1  
@dsg: Thanks, I now understand. It's a good question! But I have no answer off the top of my head. –  Joseph O'Rourke Mar 20 '11 at 13:37
    
The most straightforward (naïve?) way of doing this would be to optimize over all possible oriented boxes as a 9-dimensional space, the way your example optimizes over the 4-dimensional space of all possible spheres. Are you looking for something cleverer than this? –  Rahul Mar 22 '11 at 6:38
    
Sure, that would be a nice start. I think the hypersphere problem as I've formulated it is a second-order cone program, and there are standard tools that can solve it (but I'm pretty sure there are better methods). Can your naive formulation be solved via some standard tools? –  dsg Mar 22 '11 at 8:21

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.