Sequential dependency computation via geometric data structures (Q390107)

Let \(G_1,G_2\) be nonnegative integers, not both zero, with \(G_1\leq G_2\). A finite nonempty sequence of integers is said to be valid if the difference between successive terms is between \(G_1\) and \(G_2\) inclusive. In the gap dependency problem one has to find the minimum number of insertions and deletions required to convert a given sequence of integers \(S=\langle a_1,\dots,a_n\rangle\) into a valid sequence. This problem has applications in obtaining statistics about a database, and is known to have a solution that runs in \(O(\tfrac{G_2}{G_2-G_1}\,n\log{n})\) time. The problem can be reduced to finding, for each \(1\leq i\leq n\), the minimum number \(T(i)\) of insertions and deletions needed to transform the subsequence \(\langle a_1,\dots,a_i\rangle\) into a valid sequence ending in \(a_i\). These quantities may be computed from the recurrence relation \[ T(i)=\min\bigl\{i-1, \min_{j<i,a_j<a_i}[T(j)+i-2-j+\mathrm{dcost}(a_i-a-j)] \bigr\} \] Here \(\mathrm{dcost}(k)\) is the smallest number of insertions that are needed to make the sequence \(\langle 0\rangle\) valid, and can be computed in constant time. The authors present a novel way in which the computation of the minima over \(j<i\) and \(a_j<a_i\) in the above recurrence relation for \(T(i)\) may be transformed into an orthogonal range search. With a judicious choice of data structure, this leads to an algorithm that solves the gap dependency problem in \(O(n\log{n}\log\log{n})\) time.