# Convex hull of a convex curve as an infinite intersection of convex hull of triangles

Let $$f(x)$$ be a univariate convex curve (say $$f(x) = x^2$$) and let the domain be bounded. The goal is to prove that the convex hull of this curve in its domain can be expressed as an infinite intersection of convex hull of triangles. The sequence of convex hull is constructed as follows:

1. Uniformly partition the domain into $$k$$ partitions
2. Construct a triangle in each partition using the two tangents at the extreme points of the partition and the secant joining the extreme points,
3. Take the convex hull of the resulting $$k$$ triangles. Let the convex hull formed at iteration $$k$$ be denoted by $$A_k$$.

Now, we want to prove $$\cap_k A_k = \operatorname{conv}(y=f(x))$$. Any help is appreciated.

$k=2$ and $$f(x) = x^2$$ in the domain $$[-2, 2]$$">

• If you assume that $f$ is bounded on the domain, then $f$ is Lipschitz continuous on the domain. This should help to prove that the vertices of the triangles are not too far away from the graph of $f$.
– daw
Commented Jan 17, 2020 at 9:51
• @daw Can you be slightly more explicit. I tried doing that without much success. Commented Jan 22, 2020 at 2:50

Let me assume that the domain in question is the interval $$[a,b]$$. Let me denote by $$G:=\{ (x,f(x)): \ x\in [a,b]\}$$ the graph of $$f$$. Since $$G \subset A_k$$ by convexity of $$f$$, it holds $$conv(G) \subset A_k$$.
Let $$f$$ be bounded on the interval $$[a,b]$$. Then it is Lipschitz continuous there. Since you are talking about tangents, let me assume that $$f$$ is differentiable on the interval. Since $$f$$ is differentiable and Lipschitz continuous, we have $$|f'(x)|\le L$$ for all $$x\in [a,b]$$.
At step $$k$$, we partition the interval $$[a,b]$$ into $$k$$ subintervals of length at most $$h_k$$, with $$h_k \to0$$ for $$k\to \infty$$.
Let $$[x_1,x_2]$$ an interval of the partition. Then the two lines below the graph that define the corresponding triangle can be described by the mappings $$x\mapsto f(x_1) + f'(x_1)(x-x_1)$$ and $$x\mapsto f(x_2) + f'(x_2)(x-x_2).$$ Let $$x\in [x_1,x_2]$$. Then the distance of a point on the triangle can be bounded from above $$| f(x) - (f(x_1) + f'(x_1)(x-x_1))|,$$ i.e., by the distance of the corresponding point of one the lines to the graph.
And by the mean value theorem, $$|f(x) - (f(x_1) + f'(x_1)(x-x_1))| = |(f'(\xi)- f'(x_1))(x-x_1)| \le L |\xi-x_1| \cdot |x-x_1| \le L |x_2-x_1|^2 \le L h_k^2.$$ That is, the distance from an point $$x$$ below the graph in some triangle to the graph tends to zero for $$k\to \infty$$. If $$x$$ is a point in some triangle and above the graph then $$x\in conv(G)$$ anyway.
Let now $$x \in \cap A_k \setminus conv(G)$$. Then for all $$k$$, $$x$$ is in some of these constructed triangles and below the graph. By the arguments above $$dist(x,G) \le Lh_k^2 \to0$$. So $$x\in G$$, a contradiction, and we have $$\cap A_k \subset cong(G)$$.