Minkowski addition

In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors A and B in Euclidean space is formed by adding each vector in A to each vector in B, i.e., the setFor example, if we have two sets A and B, each consisting of three position vectors (informally, three points), representing the vertices of two triangles in R 2 {displaystyle mathbb {R} ^{2}}  , with coordinatesMinkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition: Minkowski addition plays a central role in mathematical morphology. It arises in the brush-and-stroke paradigm of 2D computer graphics (with various uses, notably by Donald E. Knuth in Metafont), and as the solid sweep operation of 3D computer graphics.For two convex polygons P and Q in the plane with m and n vertices, their Minkowski sum is a convex polygon with at most m + n vertices and may be computed in time O (m + n) by a very simple procedure, which may be informally described as follows. Assume that the edges of a polygon are given and the direction, say, counterclockwise, along the polygon boundary. Then it is easily seen that these edges of the convex polygon are ordered by polar angle. Let us merge the ordered sequences of the directed edges from P and Q into a single ordered sequence S. Imagine that these edges are solid arrows which can be moved freely while keeping them parallel to their original direction. Assemble these arrows in the order of the sequence S by attaching the tail of the next arrow to the head of the previous arrow. It turns out that the resulting polygonal chain will in fact be a convex polygon which is the Minkowski sum of P and Q.There is also a notion of the essential Minkowski sum +e of two subsets of Euclidean space. Note that the usual Minkowski sum can be written asFor K and L compact convex subsets in R n {displaystyle mathbb {R} ^{n}}  , the Minkowski sum can be described by the support function of the convex sets: