11 papers · ranked by Valyu relevance
Chao Pan, Zhicheng Lv, Xia Hua, Hongyan Li
Normalized cross-correlation is an important mathematical tool in digital signal processing. This paper presents a new algorithm and its systolic structure for digital normalized cross-correlation, based on the statistical characteristic of inner-product. We first introduce a relationship between the inner-product in…
Iago A. Carvalho, Thomas Erlebach, Kleitos Papadopoulos
We study a problem where k autonomous mobile agents are initially located on distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous mobile agent has a predefined velocity and is only allowed to move along the edges of the graph. We are interested in delivering a package, initially positioned in…
Jie Huang, Tian Zhou, Weidong Du, Jiajun Shen + 1 more
A new fast deconvolved beamforming algorithm is proposed in this paper, and it can greatly reduce the computation complexity of the original Richardson-Lucy (R-L algorithm) deconvolution algorithm by utilizing the convolution theorem and the fast Fourier transform technique. This algorithm makes it possible for…
Cunzhe Lu, Xiaogang Qi, Kai Ding, Baoguo Yu + 1 more
In complex environments such as those with low textures or obvious brightness changes, point features extracted from a traditional FAST algorithm cannot perform well in pose estimation. Simultaneously, the number of point features extracted from FAST is too large, which increases the complexity of the build map. To…
Sariel Har-Peled
We are given a directed graph G = (V, E) with n vertices and m edges, with positive weights on the edges, and a parameter k > 0. We show how to compute, for every vertex v ∈ V , its k nearest-neighbors. The algorithm runs in O(k(n log n + m)) time, and follows by a somewhat careful modification of Dijkstra's shortest…
Shay Mozes, Yahav Nussbaum, Oren Weimann
We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm on the dense…
Ali Dasdan
The Fibonacci numbers are a sequence of integers in which every number after the first two, 0 and 1, is the sum of the two preceding numbers. These numbers are well known and algorithms to compute them are so easy that they are often used in introductory algorithms courses. In this paper, we present twelve of these…
Chao Chen, Bruno da Silva, Ruiqi Chen, Shun Li + 3 more
'Chengyu Liu' 'Fernando Morgado-Dias'] Entropy is one of the most fundamental notions for understanding complexity. Among all the methods to calculate the entropy, sample entropy (SampEn) is a practical and common method to estimate time-series complexity. Unfortunately, SampEn is a time-consuming method growing in…
Michal Koucký, Michael Saks
For any T ≥ 1, there are constants R = R(T ) ≥ 1 and ζ = ζ(T ) > 0 and a randomized algorithm that takes as input an integer n and two strings x, y of length at most n, and runs in time O(n 1+ 1 T ) and outputs an upper bound U on the edit distance of dedit(x, y) that with high probability, satisfies U ≤ R(dedit(x, y)…
Fabio Cannizzo
Given an array X of N + 1 strictly ordered floating point numbers1 and a floating point number z belonging to the interval [X0, XN), a common problem in numerical methods is to find the index i of the interval [Xi , Xi+1) containing z, i.e. the index of the largest number in the array X which is smaller or equal than…
Sebastian Wild, Markus E. Nebel, Ralph Neininger
In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy's implementation in running time experiments. At that time, no precise investigations of…