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 4+ε ), for any ε > 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 2 d −4+ε ), for any ε > 0, on the complexity of vertical decompositions in dimensions d ≥ 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.