Point location in arrangements of algebraic hypersurfaces

RAFAEL GRIMSON

Timisoara, Rumania

Simposio; 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing; 2009

Given a finite family P := P1,...,Ps of polynomials in R[X1,...,Xn], the algebraic point-location problem for the family P asks to determine the connected components of the realizations of the P-sign conditions containing a query point in Rn. We prove that for each particular family of polynomials P1,..., Ps of degree bounded by d, it is possible to design a data structure that allows to solve the point location problem, whose search time grows only logarithmically in s. We briefly present two different methods. The first one is based on a binary search strategy applied to the data structure obtained from Collins’ cylindrical algebraic decomposition; this binary search is, on its turn, based on Thom’s Lemma. The complexity of the query evaluation for this method is log(s)d^2^n. The second method is based on Meiser’s algorithm for the linear case and the dialytic method. The complexity of the query evaluation for this method is log(s)d^(O(n^4)).