Evaluating geometric queries using few arithmetic operations

Rafael Grimson, Joos Heintz, Bart Kuijpers

Let $\cp:=(P_1,...,P_s)$ be a given family of $n$-variate polynomials with integer coefficients and suppose that the degrees and logarithmic heights of these polynomials are bounde…