Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications
Otfried Cheong Schwarzkopf, Micha Sharir · 1996
Let X be a collection of n algebraic surface patches of constant maximum degree in IR3.We show that the combinatorial complexity of the vertical decomposition of a single cell in the arrangement A(Z) is 0(n2+E ), for my E > CI, where the constant of proportionality de pends on E and on the maximum degree of the surfaces and of their boundaries.As an application, we obt~"n a near-quadratic motion planning algorithm for general systems with three degrees of freedom.