Geometric predicates as arrangements of hypersurfaces: Application to comparison of algebraic numbers

International audienceA lot of geometric predicates can be formulated as an arrangement of hypersurfaces (algebraic varieties) in a high-dimensional space, where each cell of the arrangement corresponds to an outcome of the predicate, and an evaluation of the predicate maps to point-location queries in this arrangement. To do this successfully, the arrangement has to be decomposed by the aid of subsidiary hypersurfaces, the degree of which plays a fundamental role in the algebraic complexity of the predicate, with respect to the input coefficients. For example, the widely used predicate of root comparison of quadratic polynomials can be mapped to an arrangement of lines and a parabola. For cubics, it becomes an arrangement of planes and a quartic surface, when a monic polynomial of degree d is represented as a point in R^d. Minimizing the degree of the subsidiary equations is an outstanding open problem