Evaluating geometric queries using few arithmetic operations

Publication date 13 December 2012

Abstract: Let

c p := (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 bounded by

d

and

h

, respectively. Suppose furthermore that for each

1 l e q i l e q s

the polynomial

P_{i}

can be evaluated using

L

arithmetic operations (additions, subtractions, multiplications and the constants 0 and 1). Assume that the family

c p

is in a suitable sense emph{generic}. We construct a database

c a l D

, supported by an algebraic computation tree, such that for each

x i n [0, 1]^{n}

the query for the signs of

P_{1} (x), ..., P_{s} (x)

can be answered using

h d^{c O (n^{2})}

comparisons and

n L

arithmetic operations between real numbers. The arithmetic-geometric tools developed for the construction of

c a l D

are then employed to exhibit example classes of systems of

n

polynomial equations in

n

unknowns whose consistency may be checked using only few arithmetic operations, admitting however an exponential number of comparisons.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Evaluating geometric queries using few arithmetic operations