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.


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.