Measures to characterize the penetration between a pair of intersecting objects are given, based on translating one object to separate from the other. Algorithms to compute a measure between convex polyhedral objects in ℜ3 are presented for two different input representations. These algorithms have linear expected running time. Details of experiments in collision detection for 3D objects using the penetration measure are also presented. © 2001 John Wiley & Sons, Inc.