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.

  • 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