Computing Minkowski sums

Minkowski sums are a useful tool for applications of geometric modelling and the sum of two given regions can be regarded as the region generated by sweeping a given region along the other. Though the sums have often been applied, and their theoretical properties studied, little has appeared concerning efficient calculation in the general case where both summands are non-convex. This thesis studies Minkowski sums of regular, bounded and path connected polygons, plane algebraic curves, and regular bounded and path-connected polyhedra in detail, discussing algorithms for their computation and establishing sharp output size estimates. It also studies some of the applications of Minkowski sums. In the polygonal case, we study the Minkowski sums of regular, bounded and path connected polygons in detail, discussing algorithms for their computation and establishing a sharp output size estimate. We also provide examples and discuss the observed time complexity and contrast it with the possible worst case complexity of the algorithms. We also present an extension of the main algorithm to the case where the polygons are unbounded. The Polyhedral algorithms presented are extensions of the planar case. In the case of algebraic curves, we show that the boundary of the Minkowski sum consists of portions of the envelope of translates of the swept curve. We show that the Minkowski-sum boundary is describable as an algebraic curve (or subset thereof) when the given curves are algebraic, and illustrate the computation of its implicit equation. We also formulate a simple numerical procedure for the case of polynomial parametric curves, based on constructing the Gauss maps of the given curves and using them to identify curve segments that are to be summed. We then present a method to extract the true boundary from the sum of these segments. We have used Minkowski sums to develop a new, simple, and efficient primitive for interpolating polyhedra: a Parameterized Interpolating Polyhedron, or PIP for short. PIPs are easily specified and edited by providing their initial and final shapes, which may be any polyhedra, and need not have corresponding boundary elements, nor be convex. We provide simple and efficient algorithms, for computing PIPs, which can be efficiently displayed using standard depth-buffer hardware.