Collision detection in aspect and scale bounded polyhedra

Abstract

Let S be a family of n polyhedral objects in d dimensions, with aspect ratio bound CY and scale factor bound (T. Let K,(S) denote the number of object-pairs in S with nonempty intersection, and let &(S) denote the number of pairs whose enclosing balls intersect. We investigate the worst-case behavior of the following ratio: p(S) = Kb(s) n + I&(S). We establish almost-tight asymptotic bounds: p(S) = O(ofilog20), and p(S) = fl(a&). The important conclusion is that the ratio is independent of n, and if S has bounded aspect ratio and scale factor, the number of enclosing ball-pair intersections is about the same as the number of object-pair intersections. Our theorem implies the following two results. First, it lends strong theoretical support to a simple and practical heuristic for collision detection (the bounding box method), used in application domains such as computer graphics and robotics, where the objects typically have constant aspect ratio and scale factor. Second, it yields an output-sensitive algorithm for reporting all intersecting pairs in a set of n convex polyhedra with constant Q and cr. Our algorithm runs in time O(n logd-’ n + K, logdml n), for d = 2,3, where I~,, is the number of intersecting object pairs. This is significantly better than the bounds achieved by the previous algorithms, which make no assumptions about the aspect and scale factors.