3 papers
cs.DS2016
Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
Omer Gold, Micha Sharir
Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as…
cs.DS2016
Dominance Product and High-Dimensional Closest Pair under
Omer Gold, Micha Sharir
Given a set of points in , the Closest Pair problem is to find a pair of distinct points in at minimum distance. When is constant, there are efficient…
cs.DS2015
Improved Bounds for 3SUM, -SUM, and Linear Degeneracy
Omer Gold, Micha Sharir
Given a set of real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Grønlund and Pettie [FOCS'14], a sim…