Sequential dependency computation via geometric data structures

We are given integers 0⩽G1⩽G2≠00⩽G1⩽G2≠0 and a sequence Sn=〈a1,a2,…,an〉Sn=〈a1,a2,…,an〉 of n   integers. The goal is to compute the minimum number of insertions and deletions necessary to transform SnSn into a valid sequence, where a sequence is valid   if it is nonempty, all elements are integers, and all the differences between consecutive elements are between G1G1 and G2G2. For this problem from the database theory literature, previous dynamic programming algorithms have running times O(n2)O(n2) and O(A⋅nlogn), for a parameter A unrelated to n  . We use a geometric data structure to obtain a O(nlognloglogn) running time.