A hierarchical method for real-time distance computation among moving convex bodies

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.