Minkowski Sum Decompositions of Convex Polygons

Abstract

Minkowski sums provide a certain way of adding polytopes together and producing a new polytope. In this paper, we give an introduction to convex polytopes and address the question of decomposing polygons and polytopes into Minkowski summands. That is, given a polytope, how can we write it as a Minkowski sum of other polytopes? We prove a theorem that allows us to use edge sets of polygons to calculate their Minkowski sum. Using this theorem, we show some other nice facts and provide an algorithm for finding Minkowski decompositions. We examine the set of all such decompositions of a given polygon, and show that it is itself a convex polytope. Provided with this paper is a Mathematica notebook that allows the user to examine and experiment with Minkowski sums. It is a nice way to get an intuition for the background and theorems in this paper, as well as supplying empirical evidence for the conjectures introduced towards the end of the paper.