Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements

Mitsuru Funakoshi & Julian Pape-Lange
The discrete acyclic convolution computes the 2n+1 sums ∑_{i+j=k|(i,j)∈[0,1,2,… ,n]²} a_i b_j in 𝒪(n log n) time. By using suitable offsets and setting some of the variables to zero, this method provides a tool to calculate all non-zero sums ∑_{i+j=k|(i,j)∈ P∩ℤ²} a_i b_j in a rectangle P with perimeter p in 𝒪(p log p) time. This paper extends this geometric interpretation in order to allow arbitrary convex polygons P with k vertices and perimeter p....
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.