How to efficiently calculate which region a polygon is in relation to a polynomial with a pencil-and-paper procedure?

Question

A polynomial splits $\mathbb{R}^2$ into 3 regions: above, below, and where the polynomial lies.

A polygon is made up of line segments. The polygon's spatial relationship to a polynomial can be one of 5 possibilities:

1. Completely above

2. Completely below

3. Completely above and on.

4. Completely below and on.

5. The polynomial runs through the polygon, so all three.

Here are some photos of a polygon and a polynomial segment:

Where 'and' mean some points are one and the other points are the other(s). So, given a polynomial how do we know if
either always be above the polynomial without intersection.

I think there should be a way to do this without requiring numerically solving when each line segment intersects (or doesn't) using a complicated polynomial equation. Kind of how we can use the cross product of vectors to see if they intersect, but are generalized? Convolutions? I am not sure how to approach this.

UPDATE: Solving a polynomial of high order or with many terms is not a satisfactory solution. I believe that there should be a way to do this without having to invert a polynomial or at least not such a complicated polynomial as the starting polynomial. Maybe some matrix using the given information, and then based on the form of the matrix, having the solution.

Answer 1

If your polynomial has degree $d$, I doubt you can avoid having to do root-finding on a polynomial of degree $d$.

Indeed, suppose there was a better method to solve your problem. Then, intuitively speaking, it seems likely we could use it for root-finding, too. Given a polynomial $p(x)$ of degree $d$ where we want to check whether it has any real roots, we'd form a region of space given by $y\ge 0$, and check the relationship between $p(x)$ and this region of space; the result (which of those 5 categories) tells us whether $p(x)$ has a root or not. You can also use it to check whether $p(x)$ has a root in some interval $x \in [\ell,u]$, by forming the region defined by $y \ge 0, x \ge \ell, x \le u$.

This is not a fully rigorous argument, because it involves an open region of space, and a polygon is closed. But it's not obvious to me how an algorithm could usefully take advantage of the closed nature of polygons to make the problem much simpler. So treat this as a 'plausibility argument' that maybe we shouldn't expect better methods for this problem.