Approximating the Geometric Edit Distance

Edit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Because many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space, the geometric edit distance (GED) has been studied. In this thesis, we focus on approximating the GED between two point sequences. Previous work has proved that there is no O(n^{2−δ})(δ > 0) exact algorithm unless SETH fails. We present a randomized O(n log² n) time O(√n)-approximation algorithm. We then generalize our result to give a randomized α-approximation algorithm for any α ∈ [1, √n], running in time O˜(n²/α²). Both algorithms are Monte Carlo and return approximately optimal solutions with high probability.