Name
Abstract | ||
|---|---|---|
The discrete acyclic convolution computes the 2n-1 sums sum_{i+j=k; (i,j) in [0,1,2,...,n-1]^2} (a_i b_j) in O(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 sum_{i+j=k; (i,j) in (P cap Z^2)} (a_i b_j) in a rectangle P with perimeter p in O(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 O(k + p(log p)^2 log k) time. Additionally, this paper presents fast algorithms for counting sub-cadences and cadences with 3 elements using this extended method. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.4230/LIPIcs.STACS.2020.30 | STACS |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitsuru Funakoshi | 1 | 1 | 2.06 |
| Julian Pape-Lange | 2 | 0 | 0.68 |