International Journal of Computational Geometry & Applications

Given a 3-SAT formula, a graph can be constructed in polynomial time such that the graph is a point visibility graph if and only if the 3-SAT formula is satisfiable. This reduction establishes that the problem of recognition of point visibility graphs is NP-hard.

We study a modified version of the partial Fréchet similarity that is motivated by real world applications, e.g. the analysis of spectroscopic data in the context of astroinformatics and the analysis of birds’ migration trajectories. In those practical applications of curve matching it is often necessary to ignore outliers while dissimilarities regarding individual directions should be weighted by individual costs.

We enable both by computing the partial Fréchet similarity between polygonal curves w.r.t. a non-uniform metric. In particular, we measure distances by a function $\mathcal{ℒ}$ that is induced by a set of weighted vectors. We discuss the approximation quality of $\mathcal{ℒ}$ regarding any $L_p$ metric and present a polynomial time algorithm for computing an exact solution of the resulting modified partial Fréchet similarity.

The article analyzes similarity of closed polygonal curves with respect to the Fréchet metric, which is stronger than the well-known Hausdorff metric and therefore is more appropriate in some applications. An algorithm is described that determines whether the Fréchet distance between two closed polygonal curves with $m$ and $n$ vertices is less than a given number $\epsilon$. The algorithm takes $O(mn)$ time whereas the previously known algorithms take $O(mn\mathrm{\text{log}}(mn))$ time.