Algorithms to compute a measure of depth of intersection between convex polygonal objects in R2 and convex polyhedral objects in R3 are presented. The algorithms have linear asymptotic complexity. Numerical experience with the algorithms is encouraging and the algorithms are shown to have linear expected running time. Parallelization of the algorithms is described. We present a new collision detection algorithm that uses the depth measure. Results of implementation are reported. © 2002 Elsevier Science Ltd. All rights reserved.