Computation of Certain Measures of Proximity Between Convex Polytopes: A Complexity Viewpoint

Four problems of proximity between two convex polytopes in R^8 are considered. The convex polytopes are represented as convex hulls of finite sets of points. Let the total number of points in the two finite sets be n. We show that three of the proximity problems, viz., checking intersection, checking whether the polytopes are just touching and finding the distance between them, can be solved in O(n) time for fixed s and in polynomial time for vayings. We also show that the fourth proximity problem of finding the intensity of collision for varying s is NP-complete