Search

The Vapnik–Chervonenkis dimension provides a notion of complexity for systems of sets. If the VC dimension is small, then knowing this can drastically simplify fundamental computational tasks such as classification, range counting, and density estimation through the use of sampling bounds. We analyze set systems where the ground set X is a set of polygonal curves in R d and the sets R are metric balls defined by curve similarity metrics, such as the Fréchet distance and the Hausdorff distance, as well as their discrete counterparts. We derive upper and lower bounds on the VC dimension that imply useful sampling bounds in the setting that the number of curves is large, but the complexity of the individual curves is small. Our upper and lower bounds are either near-quadratic or near-linear in the complexity of the curves that define the ranges and they are logarithmic in the complexity of the curves that define the ground set. [ABSTRACT FROM AUTHOR]

Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance. Since it was proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original $$O(n^2 \log n)$$ algorithm by Alt and Godau for computing the Fréchet distance remains the state of the art (here, n denotes the number of edges on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fréchet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fréchet distance between two polygonal curves in time $$O(n^2 \sqrt{\log n}(\log \log n)^{3/2})$$ on a pointer machine and in time $$O(n^2(\log \log n)^2)$$ on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth $$O(n^{2-\varepsilon })$$ , for some $$\varepsilon > 0$$ . We believe that this reveals an intriguing new aspect of this well-studied problem. Finally, we show how to obtain the first subquadratic algorithm for computing the weak Fréchet distance on a word RAM. [ABSTRACT FROM AUTHOR]

All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fréchet distance between polygonal curves in $$\mathbb {R}^d$$ under polyhedral distance functions (e.g., $$L_1$$ and $$L_\infty $$ ). We also get a $$(1+\varepsilon )$$ -approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed $$\varepsilon > 0$$ . For the exact Euclidean case, our framework currently yields an algorithm with running time $$O(n^2 \log ^2 n)$$ . However, we conjecture that it may eventually lead to a faster exact algorithm. [ABSTRACT FROM AUTHOR]

We describe a $$O(\log n )$$ -approximation algorithm for computing the homotopic Fréchet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a $$O(\log n)$$ -approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic Fréchet distance, or the minimum height of a homotopy, is in NP. [ABSTRACT FROM AUTHOR]

We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local-search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, which leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest. [ABSTRACT FROM AUTHOR]

We present a simple and practical (1+ ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ℝ. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves. [ABSTRACT FROM AUTHOR]

A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fréchet distance. Whereas efficient algorithms are known for computing the Fréchet distance of polygonal curves, the same problem for triangulated surfaces is NP-hard. Furthermore, it remained open whether it is computable at all. Using a discrete approximation, we show that it is upper semi-computable, i.e., there is a non-halting Turing machine which produces a decreasing sequence of rationals converging to the Fréchet distance. It follows that the decision problem, whether the Fréchet distance of two given surfaces lies below a specified value, is recursively enumerable. Furthermore, we show that a relaxed version of the Fréchet distance, the weak Fréchet distance can be computed in polynomial time. For this, we give a computable characterization of the weak Fréchet distance in a geometric data structure called the Free Space Diagram. [ABSTRACT FROM AUTHOR]