文章基本信息

标题：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