Godau [@Alt1995] describe an algorithm to compute the [Fréchet distance]{} based on the decision variant (that is, solving $\delta_\text{F}(P,Q) \leq \varepsilon$ for some given $\varepsilon$). Their algorithm uses a *free space diagram*, a two-dimensional diagram on the range $[0, m] \times [0, n]$. Every point $(x,y)$ in this diagram is either “free” (white) or not (indicating whether $|P(x) - Q(y)| \leq \varepsilon$). The diagram has $m$ columns and $n$ rows; every cell $(c,r)$ ($1 \leq c \leq m$ and $1 \leq r \leq n$) corresponds to the edges $p_{c-1}p_{c}$ and $q_{r-1}q_{r}$. To compute the [Fréchet distance]{}, one finds the smallest $\varepsilon$ such that there exists an x- and y-monotone path from point $(0,0)$ to $(m, n)$ in free space.

![Three event types. (A) Endpoints come within range of each other. (B) Passage opens on cell boundary. (C) Passage opens in row (or column). We scale every row and column in the diagram to correspond to the (relative) length of the actual edge of the curve instead of using unit squares for cells.[]{data-label="fig:events"}](events)

For this, only certain *critical values* for the distance have to be checked. Imagine continuously increasing the distance $\varepsilon$ starting at $\varepsilon = 0$. At so-called *critical events*, 