Given two convex polyhedra in three-dimensional space, the authors develop an algorithm to (1) test whether their intersection is empty, and (2) if so to find a separating plane, while (3) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in time 0(nlogn), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (3) (constructing the intersection) is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point. (Author)
展开▼
