What do they mean by lower envelope of parabolas?

Question

I'm studying an algorithm on distance transforms and there's a part which confuses me.

Let $G = \{0, . . . , n − 1\}$ be a one dimensional grid, and $f :G →R$ an arbitrary function on the grid. The squared Euclidean (or quadratic) one-dimensional distance transform of f defined by equation (1) is given by: $Df (p) = \displaystyle{\min _{q∈G}} ((p − q)^ 2 + f(q))$.

Note that for each point q ∈ G there is a constraint that the distance transform of f be bounded by a parabola rooted at (q, f(q)). In fact the distance transform is defined by the lower envelope of these parabolas, as shown in Figure 1. The value of the distance transform at p is simply the height of the lower envelope at that point.

What do they mean by the lower envelope of some parabolas? You can see "Figure 1", which they mention, below. Apparently, it seems envelopes are a term I just haven't heard of. Reading the definition didn't really help me and I'm not sure they refer to these envelopes in the paper.

Answer 1

If we take the formal definition of the given distance transform, $$ Df (p) = {\min_{q∈G}} ((p − q)^2 + f(q)), $$ it should be evident that the graph of $Df$ consists of portions of some of the parabolas in Figure 1. Not all of the parabolas contributed to the graph of $Df$; for example, graph of $Df$ does not come anywhere near the parabola with vertex $(1,f(1))$. But the graph of $Df$ consists of the portion of the parabola $\gamma_0$ with vertex $(0,f(0))$ to the left of the intersection of $\gamma_0$ with the parabola $\gamma_2$ with vertex $(2,f(2)),$ and then a portion of the parabola $\gamma_2$ from that intersection to whatever parabola $\gamma_2$ next intersects.

So we get a piecewise parabolic curve with a cusp in each place along the graph where the arcs of different parabolas intersect.

Figure 1 could have been improved by tracing parts of $Df.$

Answer 2

An envelope of a family of parabolas is a curve that is tangent to each member at some point. These points of tangency together form the envelope. And lower envelope is the envelope determined by the pointwise minimum (geometrically, the "lowermost point" and hence the name) of the parabolas.

Check out this, this this and this for more.