L. J. Guibas, A. Nguyen, and L. Zhang, Zonotopes as Bounding Volumes,
Symposium on Discrete Algorithms (SODA) 2003, pp. 803-812.
Zonotopes are centrally symmetric polytopes with a very special
structure: they are the Minkowski sum of line segments. In this paper we
propose to use zonotopes as bounding volumes for geometry in collision
detection and other applications where the spatial relationship between
two pieces of geometry is important. We show how to construct optimal, or
approximately optimal zonotopes enclosing given set of points or other
geometry. We also show how zonotopes can be used for efficient collision
testing, based on their description via their defining line segments
. without ever building their explicit description as polytopes. This
implicit representation adds flexibility, power, and economy to the
use of zonotopes as bounding volumes.
, author = "L. J. Guibas, A. Nguyen, and L. Zhang"
, title = "Zonotopes as Bounding Volume"
, booktitle = "Symposium on Discrete Algorithms"
, year = 2003
, pages = "803--812"