Computing the Minkowski Sum of Convex Polytopes in ^d
share
We propose a method to efficiently compute the Minkowski sum, denoted by binary operator ⊕ in the paper, of convex polytopes in ^d using their face lattice structures as input. In plane, the Minkowski sum of convex polygons can be computed in linear time of the total number of vertices of the polygons. In ^d, we first show how to compute the Minkowski sum, P ⊕ Q, of two convex polytopes P and Q of input size n and m respectively in time O(nm). Then we generalize the method to compute the Minkowski sum of n convex polytopes, P_1 ⊕ P_2 ⊕...⊕ P_n, in ^d in time O(∏_i^nN_i), where P_1, P_2, ..., P_n are n input convex polytopes and for each i, N_i is size of the face lattice structure of P_i. Our algorithm for Minkowski sum of two convex polytopes is optimal in the worst case since the output face lattice structure of P⊕ Q for convex polytopes in ^d can be O(nm) in worst case.
READ FULL TEXT