VERTICAL DECOMPOSITION OF A SINGLE-CELL IN A 3-DIMENSIONAL ARRANGEMENT OF SURFACES

Let Sigma be a collection of n algebraic surface patches in R-3 of con stant maximum degree b, such that the boundary of each surface consist s of a constant number of algebraic arcs, each of degree at most b as well. We show that the combinatorial complexity of the vertical decomp osition of a single cell in the arrangement A(Sigma) is O(n(2+epsilon) ), for any epsilon > 0, where the constant of proportionality depends on epsilon and on the maximum degree of the surfaces and of their boun daries. As an application, we obtain a near-quadratic motion-planning algorithm for general systems with three degrees of freedom.