An Efficient Algorithm for the Sign Condition Problem in the Semi-Algebraic Context

RAFAEL GRIMSON

Castro Urdiales

Conferencia; Geometric Modeling and Processing; 2010

We study the algebraic complexity of the sign condition problem for any given family of polynomials. Essentially, the problem consists in determining the sign condition satisfied by a fixed family of polynomials at a query point, performing as little arithmetic operations as possible. After defining precisely the sign condition and the point location problems, we introduce a method called emph{the dialytic method} to solve the first problem efficiently. This method involves a extit{linearization} of the original polynomials and provides the best known algorithm to solve the sign condition problem. Moreover, we prove a lower bound showing that the dialytic method is almost optimal. Finally, we extend our method to the point location problem. The dialytic method solves (non-uniformly) the sign condition problem for a family of $s$ polynomials in $RXn$ given by an arithmetic circuit $Gamma_{cal F}$ of non-scalar complexity $L$ performing $cO((L+n)^5log(s))$ arithmetic operations. If the polynomials are given in dense representation and $d$ is a bound for their degrees, the complexity of our method is $cO(d^{5n} log(s))$. Comparable bounds are obtained for the point location problem.