Boundary evaluation algorithms for Minkowski combinations of complex sets using topological analysis of implicit curves (Q2583227)

The Minkowski geometric algebra of complex sets is concerned with sets of complex numbers generated by algebraic combinations of complex values that vary independently over prescribed complex-set operands. This algebra provides an extension of real interval arithmetic to sets of complex numbers, and has applications in computer graphics and image analysis, geometrical optics, and dynamical stability analysis. The focus in this paper is on geometrically-motivated new insights and algorithms for the efficient computation of Minkowski sums, products, swept volumes, and Horner terms. Available algorithms to compute the boundaries of Minkowski sums and products invoke a dissection of the parametrized set boundaries into segment pairs, along which certain matching criteria hold. Taking the sum or product of corresponding points along each segment pair yields an unorganized set of candidate edges for the Minkowski sum or product boundary. The true boundary is obtained through a time-consuming process of culling edges that lie in the interior of the set, and organizing the remaining edges in proper order. In this paper, the authors present a new approach, whereby the matching condition is regarded as an implicit curve in the space \({\mathbb R}^n\) whose coordinates are boundary parameters for the \(n\) given sets. The analysis of the topological configuration of this curve facilitates the identification of sets of segments on the operand boundaries that generate boundary segments of the Minkowski set, and the rejection of certain sets that satisfy the matching criterion but yield only interior edges. Geometrical relations between the operand set boundaries and the implicit curve in \({\mathbb R}^n\) are derived, and the use of the method in the context of Minkowski sums, products, planar swept volumes, and Horner terms is described.