Almost tight upper bounds for vertical decompositions in four dimensions

Abstract

We show that the complexity of the vertical decomposition of an arrangement of n fixed-degree algebraic surfaces or surface patches in four dimensions is O(n/sup 4+/spl epsi//) for any /spl epsi/ > 0. This improves the best previously known upper bound for this problem by a near-linear factor, and settles a major problem in the theory of arrangements of surfaces, open since 1989. The new bound can be extended to higher dimensions, yielding the bound O (n/sup 2d-4+/spl epsi//), for any /spl epsi/ > 0, on the complexity of vertical decompositions in dimensions d /spl ges/ 4. We also describe the immediate algorithmic applications of these results, which include improved algorithms for point location, range searching, ray shooting, robot motion planning, and some geometric optimization problems.