Global Polyline Simplification Under the Fréchet Distance: Theory and Practice

Local simplification has been extensively studied. Under the Fréchet distance, the Imai-Iri algorithm computes an optimal solution in $𝒪(n^3)$ by constructing a so-called shortcut graph in which the shortest path coincides with the smallest feasible simplification. The efficiency of the graph construction step was improved in [17], resulting in a running time of $𝒪(n^2\log n)$ and significantly faster computation in practice. Furthermore, heuristics are commonly applied, such as the Douglas-Peucker algorithm with a running time of $𝒪(n^2)$ (and no quality guarantee) [7] and the approximation algorithm by Agarwal et al. [1], which runs in $𝒪(n\log n)$ and guarantees that the computed simplification size does not exceed the optimal one for a parameter $\epsilon /2$.

The concept of global simplification was touched upon in [1] and [3], but only in the context of weak simplification or when using the discrete Fréchet distance as the error measure. The systematic study of vertex-restricted global polyline simplification was initiated by van Kreveld et al. [19]. They show that neither the Douglas-Peucker nor the Imai-Iri algorithm produce optimal solutions for this problem variant, and present an exact algorithm with a running time in $𝒪(k^{\ast }{n}^5)$, where $k^{\ast }$ denotes the output size. This running time was later reduced to $𝒪(n^3)$ by Bringmann and Chaudhury [4] as well as van de Kerkhof, Kostitsyna, Löffler, Mirzanezhad, and Wenk [18]. In [4], a conditional lower bound is presented, making the existence of subcubic algorithms for global simplification in high dimensions unlikely.

The one dimensional case is the only case where subcubic algorithms are known for the Fréchet setting, in fact local and global Fréchet simplifications have the same size and can be computed in linear time. Although this result was established by Driemel et al. [9], its significance appears to have been overlooked in subsequent literature¹¹1For example, [18] rediscovered the linear time algorithm but only for the curve-restricted setting; they do not mention it for the other settings., likely because the original authors framed it within a non-optimality claim. In the setting where the start and end vertex are required to be in the simplification, their finding is, in fact, optimal.

Their algorithm can be stated simply: Include the first polyline vertex in the simplification and traverse all vertices until the first $P(i)$ outside of $[P(0)-\epsilon ,P(0)+\epsilon ]$ is found and go towards the direction where $P(i)$ leaves this range; for simplicity, assume that we go right. Maintain the right-most vertex $P(e)$ found. If $P(e)-P(i)>2\epsilon$ for the current vertex $i$, append $P(e)$ to the simplification and reverse the direction. A similar algorithm also works for the local Hausdorff setting with the small modification that we change direction when a vertex left of $P(i^{\prime })-\epsilon$ is found (or right of $P(i^{\prime })+\epsilon$ when going left), where $P(i^{\prime })$ is the previously found vertex in the simplification. The global Hausdorff setting is trivial since we only need to include the start and end vertices as well as potentially the left-most and right-most vertices. If the left-most or right-most vertex is within $\epsilon$ of the start or end, or between the two, we do not need to include them; otherwise, we do.

First, we investigate the maximum possible difference in size between optimal global and local simplification. Previous work established that there can be a constant-factor gap between them [18]. We significantly strengthen this separation by constructing a class of polylines for which optimal global and local simplification differ by a factor in $\mathrm{\Theta }(n)$. Thus, our bound is asymptotically tight, rules out local simplification algorithms as approximation algorithms for global simplification, and illustrates the significant potential of simplification size reduction when using global simplification.

To compare the simplification sizes and running times of global and local simplification algorithms in practice, we provide the first implementations²²2The implementation as well as data is publicly available at https://github.com/Ingemisco/Global-Polyline-Simplification-under-the-Frechet-Distance-Theory-and-Practice of the exact algorithms for global simplification by Bringmann and Chaudhury [4] and by van Kreveld et al. [19]. We describe several engineering techniques to significantly reduce their running times and space consumption. Furthermore, we address the fact that these algorithms rely on geometric computations prone to numerical issues. We present an implicit Fréchet framework that abstracts explicit equation solving into a small set of decision problems. We show that all algorithms discussed here, as well as many related algorithms, can be rewritten using these decision problems. This allows us to assume a weaker model of computation. In the Euclidean case, this allows us to avoid square root computations, thus operating within the regular RAM model of computation. Using this framework in our implementation yields a slower but more robust implementation. Despite the theoretical cubic running time, our experimental evaluation demonstrates that optimal solutions for polylines with hundreds of vertices can be computed in seconds. This allows us to evaluate the difference between global and local simplification sizes on practical instances for the first time. Interestingly, instances on which they do not produce the same solution size are rare and the maximum observed gap is tiny (especially compared to our theoretical worst-case gap example). Finally, using the classic Imai-Iri algorithm as a basis, we derive a global simplification algorithm that is equivalent to the one by the authors of [18] but presented in a more intuitive way. We then show how to modify this algorithm into a simple heuristic that is guaranteed to find a solution at least as good as the local optimal one. In practice, the heuristic outperforms the exact algorithms while yielding optimal solutions on almost all tested instances.

In Appendix A.1, we describe a data structure that can be constructed in $𝒪(n^4\log n)$ and returns the optimal global simplification for any given $\epsilon$ in $𝒪(\log n)$. In Appendix A.2, we provide matching lower bounds for crucial steps in the construction of the data structure.

To describe the exact algorithms concisely, we introduce the following notation.

The algorithm by van Kreveld et al. [19] uses dynamic programming with a three-dimensional table $DP$. The value stored in $DP[k,i,j]$ is the smallest $t\in [0,1]$ for which there exists a partial simplification $Q$ of $P[0\mathrm{\dots }i]$ with exactly $k$ shortcuts such that ${\delta }^F(Q,P[0\mathrm{\dots }j+t])\le \epsilon$. If no such $t$ exists, we set $DP[k,i,j]=\mathrm{\infty }$. If $t=DP[k,n,n-1]\ne \mathrm{\infty }$ for some $k$, a simplification can be extracted from $DP$ because $P[0\mathrm{\dots }n]=P$ and $P(n-1+t)$ lies on the last line segment. The smallest such $k$ is denoted by $k^{\ast }$. For $k=0$, the entries are computed trivially. For $k>0$, each layer is computed from the previous one. To compute $DP[k,i,j]$, we iterate over all $DP[k-1,i^{\prime },j^{\prime }]$ with and $j^{\prime }\le j$, and determine the minimum $t$ for which ${\delta }^F(P[j^{\prime }+t^{\prime }\mathrm{\dots }j+t],\overline{P(i^{\prime })P(i)})\le \epsilon$ (if such a $t$ exists), where $t^{\prime }=DP[k-1,i^{\prime },j^{\prime }]$. To test whether this Fréchet distance is within $\epsilon$ and obtain the respective $t$, a modified⁵⁵5We do not need to explicitly compute the Fréchet distance allowing a simpler algorithm. version of the algorithm from Alt and Godau [2] can be used which runs in $𝒪(n)$. Thus, the minimization can be performed in cubic time per cell entry, leading to a total runtime of $𝒪(k^{\ast }{n}^5)$. For better practical runtimes, we introduce the following trivial optimizations:

• $\mathrm{■}$

  Reachability: If no point on $\overline{P(j)P(j+1)}$ lies within $\epsilon$ of $P(i)$, then $DP[k,i,j]=\mathrm{\infty }$ for all $k$, and no minimization is needed.

• $\mathrm{■}$

  Local Minimality: When computing $DP[k,i,j]$, the minimization can be stopped early if the computed minimum equals ${\widehat{t}}_0(\overline{P(j)P(j+1)},P(i))$.

• $\mathrm{■}$

  Global Minimality: If $DP[k-1,i,j]={\widehat{t}}_0(\overline{P(j)P(j+1)},P(i))$, this value can be copied to $DP[k,i,j]$.

The correctness of the first optimization is straight-forward. For the local and global minimality optimizations, correctness follows from comparing with the lower bound for $DP[k,i,j]$. Finally, we note that the computations for each layer can be parallelized because they depend only on the previous layer.

To reduce the running time to $𝒪(n^3)$, Bringmann and Chaudhury split the minimization for computing $DP[k,i,j]$ into two cases: $j^{\prime }=j$ and . The value of $DP[k,i,j]$ is then the minimum of the values computed for these two cases. The case $j^{\prime }=j$ can be solved in constant time per cell entry by maintaining a minimum. The case is more complicated; they introduce the cell reachability problem to compute $n$ minimal cell entries in linear time, yielding constant amortized time per cell entry. Their modifications restructure the algorithm because of the more complex data flow. The outermost loop is over $i$ instead of $k$, resulting in total runtime of $𝒪(n^3)$ rather than the expected $𝒪(k^{\ast }{n}^2)$⁶⁶6Revisiting their conditional lower bound proof rules out $𝒪(f(k^{\ast })n^{3-\beta })$ algorithms for any $f$ and $\beta >0$, as the simplification in their reduction has constant size..

The more complicated data flow prevents the application of the optimizations discussed above for the van Kreveld et al. algorithm. Furthermore, parallelization is difficult to apply in this restructured algorithm. Thus, especially for small polylines, the van Kreveld et al. algorithm may be faster in practice.

Next, we discuss how to adapt the classic Imai-Iri algorithm, originally proposed for local simplification, to the global case. This yields an algorithm equivalent to the one from the authors of [18] but provides a fresh perspective. We argue that this algorithm achieves cubic (and possibly subcubic) runtime for certain classes of polylines and use this observation to formulate a new heuristic that has the potential for improved running time in practice.

We demonstrate the conversion using the Alt and Godau algorithm [2], which decides whether ${\delta }^F(P,Q)\le \epsilon$. For simplicity, we assume $Q=\overline{uv}$ is a line segment (as in the minimization step of van Kreveld et al.’s algorithm). The general case and other algorithms convert similarly. Let $n$ be the length of $P$. In the explicit variant, the value ${\widehat{t}}_0(e,u)$ is computed and stored dynamically. In our implicit variant, we instead store restrictions (vertex indices). First, test whether $\delta (u,P(0))\le \epsilon$ and $\delta (v,P(n))\le \epsilon$. For general Minkowski distances, this test may involve higher-order roots, but it can be performed without them by raising both sides to the appropriate power. The algorithm tracks the earliest reachable point on $Q$ while traversing $P$. We replace these points with restrictions. The initial restriction is $P(0)$; note that $P(0)\leftrightarrow Q$ because $\delta (P(0),Q(0))\le \epsilon$. Let $r$ be the current restriction. When processing vertex $P(i)$, test whether $r\stackrel{𝑄}{\to }P(i)$. If so, update $r\leftarrow P(i)$. If $r\stackrel{𝑄}{\leftarrow }P(i)$ keep $r$. Otherwise, report ${\delta }^F(P,Q)>\epsilon$.

In Listing 1, we show both the explicit and implicit version of the algorithm from Alt and Godau as used in the algorithm from van Kreveld et al. This version takes as additional input a parameter $t^{\prime }\in [0,1]$ and outputs a $t\in [0,1]$ or $\mathrm{\infty }$ as mentioned in Section 4.1.

The semiexplicit approach provides another method for implementing Euclidean Fréchet algorithms without square roots. It combines characteristics of both explicit and implicit algorithms. In the Euclidean case, the decision problems require only comparisons of the form $a-\sqrt{b}\le c\pm \sqrt{d}$, which can be decided without evaluating square roots. The idea of semiexplicit Euclidean variants is to define data types that store such $(a,b)$ and $(c,d)$ and define appropriate comparison operators between them. In programming languages that support parametric polymorphism, the code for semiexplicit and explicit variants can be identical. For example, in C++, we can use templates and operator overloading to implement algorithms. By instantiating the templates with different data types, we obtain both explicit and semiexplicit variants. This makes it straightforward to implement both variants while retaining the benefit of avoiding square root computations.

We use synthetic and real-world data in our experiments. Synthetic polylines were generated using a custom method that takes as input the vertex count, minimum and maximum segment lengths $m$ and $M$, and maximum deviation angle $\alpha$ between consecutive line segments (e.g., ${180}^{\circ }$ means no restriction, $0^{\circ }$ yields a straight line). Smaller values of $\alpha$ produce smoother polylines. Deviation angles are drawn uniformly from $[-\alpha ,\alpha ]$. Segment lengths are generated via inverse transform sampling using the formula $\text{length}=\sqrt[d]{m^d+(M^d-m^d)U}$, where $U\sim \text{Uniform[0,1]}$ and $d$ is the dimension. This ensures that the vertices are distributed uniformly in the annulus section defined by $d,m,M$, and $\alpha$. We set $m=2$ and $M=10$, respectively. We created two benchmarks sets; example instances from each are shown in Figure 5:

• $\mathrm{■}$

  well-behaved (w) polylines with a maximum angle of ${60}^{\circ }$, and

• $\mathrm{■}$

  non-well-behaved (n) polylines with a maximum angle of ${180}^{\circ }$.

Unless stated otherwise, we use $\epsilon =2$ in all experiments. We use this because for our choices of parameters for data generation it often yielded interesting simplifications. Smaller $\epsilon$ tend to use almost all vertices and large $\epsilon$ often use a constant number of vertices. The choices for $m,M,d,\alpha$ for the data generation were arbitrary.

Our real-world data consists of 100 openly available GPS traces¹⁰¹⁰10Data from https://www.openstreetmap.org/traces/ uploaded December 29–30 and January 9, converted from GPX. with vertex counts between 100 and 800. We used the longitude and latitude coordinates, translated each trace to start at the origin, and scaled them so that the median segment length is 10. Translation does not affect the simplifications, and scaling only changes the effective value of $\epsilon$.

First, we compare the effect of our three proposed optimizations on the runtime of the KLW algorithm (Figure 7). We observe that they significantly reduce the running time for all norms and algorithm configurations. For example, in the implicit Euclidean setting, the runtime decreases from about 6.0 seconds (non-well-behaved) and 5.4 seconds (well-behaved) to less than 300 milliseconds for both.

Next, we compare the KLW algorithm (with all optimizations) and the BC algorithm (Figure 7). The KLW algorithm is competitive for polylines of length up to 200, after which the BC algorithm dominates. The BC algorithm’s runtime is smooth due to its rigid structure which yields a cubic running time on all instances.

Nevertheless, our implementation allows us to compute exact global simplifications for polylines with up to 800 vertices within a few seconds (see Figure 8). For larger polylines, space consumption becomes the bottleneck on our hardware. On the feasible instances, we also compare the scalability of the BC algorithm and our heuristic in the same figure. The heuristic is approximately 200 times faster, and this speedup grows significantly for larger polylines. Moreover, since the heuristic requires only quadratic space, it can be applied to substantially longer polylines. The heuristic achieved optimal results on all instances, which makes the comparison to the optimal algorithm more fair.

One of the main practical questions is how much global and local simplifications differ on different types of polylines. To answer this, we compare the sizes of optimal global and local simplification of well-behaved and non-well-behaved polylines (Figure 10). The plot contains four data sets, but they are visually difficult to distinguish because the output sizes are, somewhat surprisingly, almost identical for local and global simplification. Indeed, for well-behaved polylines, the sizes were always identical, while for non-well-behaved polylines we observed only marginal differences. The plot also shows that well-behavedness dramatically affects simplification sizes because much longer shortcuts are feasible on well-behaved data. To compute the local simplifications we used a naïve implementation of the Imai-Iri algorithm. This already outperforms the BC algorithm as can be seen in Figure 10.

Given the small difference between global and local simplification sizes, our heuristic (which by construction produces an output size between those two) is nearly always optimal. Testing one million random polylines of length 100, we found only eight instances where the heuristic was non-optimal, with the worst case requiring two extra vertices. By comparison, approximately 10% of these polylines had differing local and global sizes.

To ensure that the similarity between global and local simplification sizes is not an artifact of our parameter choices, we performed an additional experiment with 500000 polylines of 150 vertices each. These were generated with random maximum segment lengths and deviation angles, as well as random $\epsilon$. In this experiment, the average difference in size was 0.3 vertices, with a maximum difference of 8 vertices.

Finally, we compare the runtime and the result size of the BC algorithm, the local algorithm and the heuristic on the real-world data using $\epsilon =2,8,32,128$. Here, the heuristic was always optimal. The local simplification was suboptimal on only 5 out of the 400 test cases. We also compute for each $\epsilon$ the total runtime of the BC algorithm and of the heuristic and show the ratio in Table 2. For small $\epsilon$, the heuristic is almost 90 times faster, while for larger $\epsilon$ it is still 12 times faster than the BC algorithm. We also compare the heuristic against our implementation of the local Imai-Iri algorithm. Surprisingly, it is only 2-4 times slower, which illustrates that the overhead introduced by the interval handling in the heuristic is rather small.

In conclusion, simply using local simplification is the most efficient way to obtain a simplification of good quality in practice (especially as it can be computed even faster than with Imai-Iri [17]). However, our heuristic also scales well and occasionally produces better solutions. On our example instance that illustrates the $\mathrm{\Theta }(n)$ gap between global and local simplification, the heuristic indeed produces the optimal results.