ABSTRACT
Over ten years ago, Guibas, Ramshaw, and Stolfi [8] introduced the kinetic framework for Computational Geometry in two dimensions. They augmented the standard boundary representation of planar shapes via polygons or closed curves with certain additional infor mation, to make them into closed tracings. The advan tage of tracings is that they admit of a multilinear cal culus of operations that generalizes standard boolean operations on shapes such as union, intersection, set difference, etc. A particular accomplishment of the ki netic framework was to define the operation of convo lution on planar tracings and to illustrate its use in a variety of algorithmic problems. Loosely speaking, the convolution B * R of two tracings B (the barrier) and R (the robot) is another tracing that encodes the inter action of B with all possible translations of a copy of R mirrored through the origin. The convolution allows us to transform problems about two tracings B and R into problems about a point and a composite tracing, the convolution B * R. A related composition concept is familiar in robotics, under the names Minkowski sum or configuration space obstacle [15, 14]; but that con cept lacks the advantageous multilinear structure of the convolution.
