Polynomial threading through a monotone corridor

Question

I have a need to find a polynomial of minimal degree that connects two points and stays within a given "corridor," by which I mean an $x$-monotone polygon. Here is an example:

---

           

---

The point $s=(0,3)$ needs to be connected to the point $t=(3,1)$ while remaining inside the $x$-monotone polygon $P$ illustrated. (Here "$x$-monotone" means that every vertical line meets the polygon in an interval or the empty set.) In the case illustrated, a cubic curve suffices, and no quadratic (or linear) curve suffices.

Q. Given data as depicted (start & end points $s$ & $t$, an $n$-vertex $x$-monotone polygon $P$), is there an algorithm to find a polynomial of minimal degree that connects $s$ to $t$ and remains within $P$?

Even an inefficient algorithm sketch would be appreciated, as I am not seeing any algorithm.

Answer 1

A much more efficient approach can be based on semidefinite programming feasibility testing. Namely, it is well-known that global nonnegativity of a degree $2d$ polynomial $g(x)$ is equivalent to existence of a decomposition of $g$ into a sum of squares of polynomials, which in turn is equivalent to existence of a postitive semidefinite $(d+1)\times (d+1)$ Hankel matrix $H$ so that $g(x)=X^\top HX$, where $X$ is the vector of monomials $X=(1,x,x^2,\dots,x^d)$. The condition $g(x)=X^\top H X$ is a positive semidefinite feasibility problem (each coefficient of $g$ gives a linear equation on entries of $H$, and $H$ must be p.s.d.).

In our case we need certificates of nonnegativity (or non-positivity, which is the same up to sign thing) of polynomials of the form $g(x):=f(x)-ax-b$ on intervals $\alpha \leq x<\beta$. Change of variable $x\to \frac{\alpha+\beta bt^2}{1+t^2}$ allows one to specify the latter as global nonnegativity of the rational function $g\left(\frac{\alpha+\beta bt^2}{1+t^2}\right)$, which is equivalent, after clearing denominators, to global nonnegativity of certain polynomial $\tilde{g}(t^2)$, with coefficients linear functions of coefficients of $f$.

Thus, for every segment $i$ of our region we get a polynomial $\tilde{g}_i(t^2)$, global nonnegativity (or nonpositivity) of which we encode as above, ending up with a semidefinite programming feasilility problem with block-diagonal matrix, each block Hankel, and free variables corresponding to coefficients of $f$.

Answer 2

The ellipsoid method applies to this problem: once you fix a degree, the space of polynomials threading through your corridor is a convex set. Given any polynomial, if there is a point on the graph which lies outside the corridor then that point provides a linear inequality (i.e. hyperplane) separating your polynomial from your desired convex set. You can test whether such a point exists, and find it if it does, using the theory of Sturm chains (to save time, you could first test a few random points on the graph before jumping to Sturm chains).

This should give a reasonably fast numerical algorithm. It won't work if the set of polynomials that fit has measure zero, or measure below some constant related to your numerical precision. You can also find an exact algorithm by either using Sturm chains cleverly or just falling back on the Tarski–Seidenberg theorem.

Edit: Sturm chains are a great tool and deserve to be more widely known. They let you exactly count the number of real roots of a real polynomial in any given interval. In particular, you can use Sturm chains together with binary search to find arbitrarily good approximation to the real roots.

Suppose WLOG that a polynomial $f(x)$ has no double roots, and use the Euclidean algorithm for $\mathbb{R}[x]$ to produce a sequence of polynomials $f_i(x)$ of strictly decreasing degrees with $f_0 = f, f_1 = f'$, and $f_{i-1} + f_{i+1}$ a multiple of $f_i$ for $i \ge 1$, ending with a constant polynomial. For any real number $x$, define $\text{sc}_f(x)$ to be the number of sign changes in the sequence $f_0(x), f_1(x), ...$ (ignoring internal $0$s). Then the number of real roots of $f$ in the half-open interval $(a,b]$ is just $\text{sc}_f(a) - \text{sc}_f(b)$.

(A possible issue here is that when $f$ is very close to having a double root, applying the Euclidean algorithm to $f, f'$ might be numerically unstable.)

Answer 3

If one just wants an algorithm: for a fixed degree $d$ of $f$, the condition that the graph of $f$ stays in the corridor and passes through given points gives you a semialgebraic set. Indeed, the condition of passing through a point is a (linear) equation on the coefficients of $f$; the condition of not crossing a segment needs a quantifier on $x$ (e.g. if $f$ stays below the line $\ell_i$ one writes $(\forall x_i) (a_i\leq x_i \leq b_i\rightarrow f(x_i)<\ell_i(x_i))$. So in total you will have a quantified variable $x_i$ for each segment, and $d+1$ variables for the coefficients of $f$.

By Tarski, non-emptiness of such a set is algorithmically decidable, and there are nowadays much better algorithms than Tarski's orginal one, see e.g. Basu, Pollack, Roy Algorithms in Real Algebraic Geometry.

Needless, to say, this allows you to solve much more general problems of this sort, and isn't really efficient in practice.