General Setup
Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which every $f_i \geq 0$. If $V$ is compact, then there is an algorithm, doubly exponential in $n$, to impose a CW structure on $V$ via the so-called cylindrical algebraic decomposition. (This is well-known and well-written in, say, Ch 5 of the book by Basu, Pollack and Roy)
Special Case
If we restrict to the case where all $f_\bullet$s in sight are affine-linear, then $V$ becomes an intersection of closed half-spaces. Now super-fast techniques for triangulating $V$ are available from computational geometry (a quick google search for fast half space intersection reveals a paper from 1978 that exploits convex hull computations to do the job in essentially $O(k \log k)$ time for $k$ polynomials). I'm sure there are people here who know even better techniques from the last few decades.
Stuck in the middle with you
A colleague faces the problem of efficiently cellulating $V$s that arise from $f_\bullet$s which are really nice, but not affine linear. In particular, each of the $f_i(x_1,\ldots,x_n)$ is a sum of square-free monomials with coefficient $\pm 1$ plus a constant. For instance, with three variables $x,y,z$ we might have polynomials like:
$$xy - yz + 3, \quad xyz - 1.03, \quad xz + yz - x$$
but no $3xy + 1$, or $x^2z$, or $x^3y-z$ etc. This appears to be a harder situation than the half space intersection, but considerably nicer than the sets generally handled by cylindrical algebraic decomposition. Here's the question:
Are there reasonably efficient algorithms -- lying strictly between $O(n \log n)$ and $O(\exp(e^n))$ -- which will impose a cell structure on $V$'s arising from this restricted class of $f_\bullet$'s?
Or are we confined to a super-exponential complexity the minute we leave affine hyperplane land?
