Finding the intersection of two convex polyhedra

Given two convex polyhedra in three-dimensional space, we develop an algorithm to (i) test whether their intersection is empty, and (ii) if so to find a separating plane, while (iii) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in timeO (nlogn), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (iii) (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.