Partial answer: about to the first question:
Let's make a change of variables to aid intuition: let $y_i = x_1+...+x_i, (i=1,..., n)$, then the region $D_i$ is described as $f_i(y_{i-1}) \le y_i - y_{i-1} \le g_i(y_{i-1})$, and, taking $\tilde f_i(u) = f_i(u) + u$, etc., we can write $D_i$ condition defining $D_i $ as $\tilde f_i(y_{i-1}) \le y_i \le \tilde g_i(y_{i-1})$. I'll drop the $\tilde \; $ going foward.
Let's also assume that the linear function $f$ to be minimized is not constant.
Since the condition defining $D_i$ bounds each dimension, one at a time, $D = \cap_i D_i$ is compact, so $f$ attains a minimum in $D$. Since the gradient of $f$ is not null, the point that affords the minimum cannot be in the interior of $D$, so it is a boundary point.
What you call a "vertix" can be made more precise. A point of a set is call extreme iff it is not contained in the relative interior of a segment with end-points in the set. For example, in two dimensions, consider the set $ D = \{(x_1,x_2) | -2 \le x_1 \le 2 \text{ and } -1 \le x_2 \le max(|x_1|,1-|x_1|) \}$ the point $(0,1)$ is a boundary point that is not extremal, because the segment with endpoints $(-1,1), (1,1)$ has endpoints in $D$, and contains $(0,1)$ in is relative interior.
(Note: the concept of extreme points appears in relation to convex sets. I used it as it would apply to the convex hull of the underlying set.)
Now if $f$ attains its minimum at a non-extereme point, then it must be constant along the segment containing the non-extemal point ($f$ restricted to the segment is affine, so it is minimized at the boundaries, or it is constant). Continue the segment until it hits a face of $D$ and argue by induction on the affine dimension of the polytope $D$.
Minkowski's theorem (or Krein-Milman theorem in locally convex Housdorf vector spaces) says that a compact convex is the convex hull of its extreme points, but if $K = \text{ closed convex hull of }D$, then the extreme points of $K$ must lie in $D$, else they will be convex combinations of other points in $K$.
So, to sum up:
1) $f$ attains its minimum at extreme points of $D$
2) the convex hull of $D$ is generated by the exteme points of $D$
$$ \ll \gg \fallingdotseq \doteqdot \doteqdot \doteqdot \doteqdot \risingdotseq \ll \gg$$
As for the second part (computing the convex hull of $D$), your problem is essentially 2 dimmensional, because the functions involved depend on only one variable. If $g_i^* = \text{ least concave majorant of }g_i$, i.e.:$g_i^*(u) = \inf\{h(u)| h \text{ is concave and } g_i(\zeta) \le h(\zeta) \text{ for all }\zeta\}$, then $g_i^*$ is convave. Similarly define $f_i^* = \text{ greatest convex minorant of } f_i $.
Because $g_i$ is piecewise linear, so is $g_i^*$, and because it is a least concave majorant, it can be written as
$$ g_i^*(u) = \min_t\{ b_{it} + m_{it}\; u \}$$
for a finite family of affine functions $u \mapsto b_{it} + m_{it}\:u$.
Likewise, $f_i^*$ can be written as
$$ f_i^*(u) = \max_s\{ \beta_{is} + \gamma_{is}\; u \}$$
for some finite family of affine functions.
There are computer algorithms to compute the convex envelope of a finete set of points on the plain, i.e.: ponts in 2D. I suspect those algorithms can be make to work to find the concave majorant, and convex nimorants above (this is the point where my answer has a gap....).
Why looking at $f_i^*, g_i^*$? Because the convex hull of $D$ can be written in terms of these functions as:
$$ f_i^*(y_{i-1}) \le y_i \le g_i^*(y_{i-1}) \;\;\;(i=1,..,n) \tag{1}, $$
and, recalling the structure of $f_i^*, g_i^*$, (1) is a description of the convex hull of $D$ in terms of hyperplanes. In all its glory, the convex hull of $D$ is: for all $i$,
$$ \begin{align}
y_i &\le b_{it} + m_{it}\; y_{i-1} &\text{ for all $t$}\\
\beta_{is} + \gamma_{is}\; y_{i-1} &\le y_i &\text{ for all $s$}
\end{align} \\
$$.
