ALMOST TIGHT UPPER-BOUNDS FOR THE SINGLE-CELL AND ZONE PROBLEMS IN 3 DIMENSIONS

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement of n low-degree algebraic surface patche s in S-space. We show that this complexity is O(n(2+delta)), for any e psilon > 0, where the constant of proportionality depends on epsilon a nd on the maximum degree of the given surfaces and of their boundaries . This extends several previous results, almost settles a 9-year-old o pen problem, and has applications to motion planning of general robot systems with three degrees of freedom. As a corollary of the above res ult, we show that the overall complexity of all the three-dimensional cells of an arrangement of n low-degree algebraic surface patches, int ersected by an additional low-degree algebraic surface patch sigma (th e so-called zone of sigma in the arrangement) is O(n(2+delta)), for an y epsilon > 0, where the constant of proportionality depends on epsilo n and on the maximum degree of the given surfaces and of their boundar ies.