4 portance of collision detection extends to several areas like robot motion planning, dynamic simulation, virtual reality applications and it has been extensively studied in robotics, computational geometry, and computer graphics for more than a decade 3, 4, 11, 13, 17, 41, 43, 45, 51, 53, 63 . Yet, there is no practical, e cient algorithm available yet for general geometric models to perform collision detection in real time. Recently, Pentland has listed collision detection as one of the major bottlenecks towards real time virtual environment simulations 69 . In this thesis, we present an e cient algorithm for collision.
