Computing convolutions by reciprocal search (Q1091816)

The paper deals with algorithms for geometric convolution operations and the proposed solutions are of linear time complexity in the worst case with respect to the input size plus the output size. In a reciprocal search problem, for objects of two different types A and B all pairs of objects have to be computed which are connected by a specified relation. For this relation R it is assumed that from xRy it follows that either \(x\in A\) and \(y\in B\), or \(x\in B\) and \(y\in A\). Reciprocal search problems as intersection of contiguous chains of intervals, and intersection of convex subdivisions are characterized to be subproblems of operations as convolution of polygonal tracings in two dimensions, or polyhedral tracings in three dimensions.