This paper presents the Hierarchical Walk, or H-Walk algorithm, which maint
ains the distance between two moving convex bodies by exploiting both motio
n coherence and hierarchical representations. For convex polygons, we prove
that H-Walk improves on the classic Lin-Canny and Dobkin-Kirkpatrick algor
ithms. We have implemented H-Walk for moving convex polyhedra in three dime
nsions. Experimental results indicate that, unlike previous incremental dis
tance computation algorithms, H-Walk adapts well to variable coherence in t
he motion and provides consistent performance. (C) 2000 Elsevier Science B.
V. All rights reserved.