Lower convex envelope of polynomial functions

Question

Let $P\in{\mathbb R}[X]$ be a polynomial and $[a,b]$ be a bounded interval. Of course, the graph of $P$ is an algebraic set. I am interested in the lower convex envelope $\bar P$ of $P|_{[a,b]}$. It seems to me that its graph is semialgebraic. However I am not at all familiar with real algebraic geometry. Is there a clear justification ?

At least, the graph of $\bar P$ is the union of arcs of the graph of $P$, together with bi-tangents. The latter are obtained by an elimination in a system of two algebraic equations.

Same question when replacing $P$ by $\min(P,Q)|_{[a,b]}$ where $P$ and $Q$ are two polynomials.

Perhaps my question looks obvious for specialists, in which case I should be happy with a proper reference.

Answer 1

The answer is yes, but not in the most exciting way. The idea is to write the envelope in the first-order logic and then kill the problem with quantifier elimination for the theory of real-closed fields.

For example, we can describe the envelope as the set of points $(z, w)$ such that for all $x, y\in [a, b]$ we have $(z, w)$ is above or on the segment between $(x, P(x))$ and $(y, P(y))$ but for any $t > 0$ there are $x, y$ such that this is not true for $(z, w-t)$. One can write it out as a first-order formula of quantifier degree 6 or so. Then, running the elimination algorithm and then reducing the result to a disjunctive normal form we get the expression as a semi-algebraic set (small caveat here is that one should treat $a, b$ and the coefficients of $P$ as free parameters and the resulting semi-algebraic set of course depends on these parameters). Note that one can also bound the number of pieces of this semi-algebraic set in terms of the degree of $P$ only (something like $2^{2^{O(deg P)}}$ or whatever the complexity of the quantifier elimination algorithm).

Of course, this strategy can be easily modifed to two or more polynomials and many other situations.