The problem of paving the solution of
polynomial inequalities with rectangular boxes has many applications in
real geometry: among the most important ones are volume computation of
semi-algebraic sets, and uniform point sampling. Consider the inequality
p>0, where p is a multivariate polynomial. The problem of box paving
consists in approximating the set of solutions of p>0 with
rectangular boxes. In the framework of spatial subdivision tree
algorithms, the main issues are: 1. the design of a sufficient criterion
to detect if p has no real zero in a given box 2. the design of
heuristics to split a box when the criterion doesn't allow us to
conclude Many approaches have been used to address these issues,
including Taylor expansion, Bernstein expansion, adapted narrowing
operators... On another hand, while the Chebyshev polynomials have very
good properties for numerical approximations of functions, they have
rarely been used in the context of multi-dimensional box paving. Indeed,
we will show that the Chebyshev expansion has very nice properties for
the problem of box paving, and we will present the results we obtained
with a high-level implementation in maple.
|