This paper presents an efficient collision detection algorithm the performance of which is independent of animation speed. Most of the previous collision detection algorithms are incremental and discrete methods, which find out the neighborhood of the extreme vertex at the previous time instance in order to get an extreme vertex at each time instance. However, if an object collides with another one with a high torque, then the angular speed becomes faster. Hence, the candidate by the incremental algorithms may be farther from the real extreme vertex at this time instance. Therefore, the worst time complexity nay be $O(n^2)$, where n is the number of faces. Moreover, the total time complexity of incremental algorithms is dependent on the time step size of animation because a smaller time step yields more frequent evaluation of Euclidean distance. In this paper, we propose a new method to overcome these drawbacks. We construct a spherical extreme vertex diagram on Gauss Sphere, which has geometric properties, and then generate the distance function of a polyhedron and a plane by using this diagram. In order to efficiently compute the exact collision time, we apply the interval Newton method to the distance function.