# Best polygonal approximation to a polynomial $\pm$ c

Let a planar region $R$ be defined by the vertical range bounded by a polynomial $f(x) \pm c$ with $c>0$ a constant, and with $x$ varying between the smallest and largest roots of $f(x)$. For example, \begin{eqnarray} f(x)&=& (x - 1)^2 (x - 2) (x - 3) (x - 4)\\ f(x) &\pm& \tfrac{1}{2} \end{eqnarray} within $x \in [1,4]$.

Now I would like to connect the smallest and largest roots of $f(x)$ with a polygonal line of fewest links that remains in $R$. In the example, between $(1,0)$ to $(4,0)$:

Here, $4$ (red) links within (the blue) $R$ suffice, and $3$ are insufficient.

Let $L(f,c)$ be the fewest links to connect the extreme roots within the region $R$ bounded by $f \pm c$.

As $c \to 0$, $L(f,c) \to \infty$, except for very special $f$. And as $c \to \infty$, $L(f,c) \to 1$. In the example above, when $c \gt 2.63628$, $L(f,c)=1$, because then the min of $f(x)$ at $x\approx 3.65374$ is raised by $+c$ to lie above the $x$-axis so that $(1,0)$ can see $(4,0)$ directly horizontally.

So, finally!, my question is:

Q. Given a fixed polynomial of maximum degree $d$ ($d{=}5$ in the above example), how does $L(f,c)$ vary as a function of $c$?

I am ultimately interested in calculating $L(f,c)$ for specific $f$ and $c$, but that does not seem straightforward, so I first seek some insight into the overall behavior.

## 1 Answer

This isn't really about polynomials, just about how big $|f''|$ gets. For small $c$, a segment of length $\delta$ must have $|f''| \, \delta^2 \ll c$, so for fixed nonlinear $f$ it will take about $c^{-1/2}$ segments.

• ("length $\delta$" in the $x$-direction, naturally.) – Noam D. Elkies Jun 7 '15 at 3:51
• I see, using a quadratic approximation. Clever & clean---Thanks! – Joseph O'Rourke Jun 7 '15 at 12:36