4
$\begingroup$

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.

  • 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?2011-03-20
  • 0
    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.2011-03-20
  • 1
    @dsg: Thanks, I now understand. It's a good question! But I have no answer off the top of my head.2011-03-20
  • 0
    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?2011-03-22
  • 0
    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?2011-03-22
  • 0
    @dsg: If you include "@name" in your comment, the other user gets notified of it. To address your comment, I don't know if my naive formulation can be solved efficiently using standard tools, but it seems unlikely. The difficulty as I see it is that unlike the spherical case, you need three degrees of freedom to describe the orientations of the box, which do not form a vector space at all. (The space of rotations can be parametrised as the unit 4-sphere in the quaternions, but that isn't a nice convex constraint either.)2011-03-22
  • 0
    @dsg: aren't you basically looking for a set of orthogonal (affine) hyperplanes that enclose your set of points? That is how polyhedral norms are defined. This is just a suggestion but you may be able to formulate your problem as: look for $2n$ vectors $a_1$ through $a_{2n}$ in $\mathbb{R}^n$ and $2n$ scalars $b_1$ through $b_{2n}$ such that $a_i^T x - b_i \geq 0$ and $a_{2i}^T x - b_{2i} \leq 0$ for all $i = 1, \ldots, n$ and all $x \in S$. You may impose $\|a_i\| = 1$ and you need $a_i$ parallel to $a_{2i}$ (you could choose them equal) and $a_i \perp a_j$ ($j \not \in \{i,2i\}$).2011-10-28

0 Answers 0