Any convex 3-dimensional object (i.e., a body such that the line segment between any two points in its volume falls entirely within the volume)

with flat sides can be described as the set of points (x, y, z) satisfying a series of linear constraints24.

For example, a 3-by 5-by 9-meter box with one corner at the origin can be modeled as 51x, y, z2: 0 … x … 3, 0 … y … 5, 0 … z … 96 Suppose that a stationary object is described in this way by constraints aix + biy + ciz … di i = 1,c, 19 and that a link of a robot arm is described at its initial position by the constraints pjx + qjy + rjz … sj j = 1,c, 12 The object and the link do not intersect at that initial position, but the link is in motion. Its location is being translated from the initial location by growing a step a 7 0 in direction 1x, y, z2.

Formulate an LP in terms of decision variables x, y, z, and a to find the smallest step (if any) that will produce a collision between the object and the link, and indicate how the LP would detect the case where no collision will occur.