文章基本信息
- 标题：Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements
- 本地全文：下载
- 作者：Mitsuru Funakoshi ; Julian Pape-Lange
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：154
- 页码：30:1-30:16
- DOI：10.4230/LIPIcs.STACS.2020.30
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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. Also, this extended algorithm only needs ð'ª(k + p(log p)² log k) time. Additionally, this paper presents fast algorithms for counting sub-cadences and cadences with 3 elements using this extended method.
- 关键词：discrete acyclic convolutions; string-cadences; geometric algorithms; number theoretic transforms
