Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb R^N$ with each entry of $w$ in the range $[0,1]$. In other words I'd like to find the image of the unit hypercube in $\Bbb R^N$ under the map represented by $A$. Does there exist an algorithm that runs in time polynomial in $N$?

Everything I've thought of so far is exponential, basically looping over the $2^N$ vertices of the hypercube. The problem is similar to that of determining the convex hull of a given set of points, except that the entries in $w$ needn't sum to $1$. Obviously taking the convex hull of all $2^N$ points would work, but it's exponential again.

My motivation is that I want to determine the range of colours that can be seen under a given light source, based on the spectral power distribution of the light source and the responsivity curves of the three cone cells in the eye.


I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient Algorithm for Generating Zonohedra (PostScript file) by Paul Heckbert.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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