Finding the Intersection of Two Convex Polyhedra.

Given two convex polyhedra in three-dimensional space, we 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 0nlogn, 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