# Determine image of hypercube under linear map

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 which is fast even when $$N$$ is large?

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.