Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions (Q2475344)

Minkowski sums and specific types of geometrical convolution are heavily used in computer-aided geometric, image processing, computer graphics and animation, path planning for robots and so forth. The paper presents a new approach based on topological arguments to compute Minkowski sums \(\mathcal{A}\bigoplus \mathcal{B}= \{\mathbf{a}+\mathbf{b}\mid \mathbf{a}\in \mathcal{A},\text{ and }\mathbf{b}\in \mathcal{B}\}\), where \(\mathcal{A},\mathcal{B}\subset\mathbb{R}^2\) have smooth curved boundaries. The problem consists in designing algorithms to compute efficiently \(\mathbf{\alpha}(u)\bigoplus \mathbf{\beta}(u)\), where \(\mathbf{\alpha}\) and \(\mathbf{\beta}\) are closed \(C^2\) curves in \(\mathbb{R}^2\) which describe the boundaries \(\partial \mathcal{A}\) and \(\partial \mathcal{B}\), respectively. These procedures should be able to minimize intermediate calculations which do not contribute to the final result (internal edges must be discarded). In this respect, the authors present a new algorithm which employs a decomposition of the Minkowski sum envelope into smooth segments along which the \(x\) and \(y\) coordinates vary monotonically. Many of the ideas and methods developed in relation to this algorithm can be extended to other geometrical convolutions in \(\mathbb{R}^2\).