Linear mapping of sliced hyperbox

Yaron Berman yaronber at
Tue Oct 5 10:43:33 PDT 2004


It is well known that a linear mapping of an n-dimensional hyperbox is a
zonotope, and when the mapping is to R^2, it is simply a convex
centrally symmetric polygon with at most 2n vertices, which is easy to
compute (in O(nlogn) time). 
My question is about the linear map of a hyperbox intersected with a
halfspace whose boundary contains the origin (which is also the center
of the box), that is a box sliced through its center. 
Is there some efficient way to compute the map (still a convex polygon),
other than enumerating all the 2^n vertices of the sliced box and
computing the convex hull of their map? If there is an efficient method,
can it be extended to the case of a box intersected with a cone?

Thanks very much for the assistance,

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list