ALMOST TIGHT UPPER-BOUNDS FOR LOWER ENVELOPES IN HIGHER DIMENSIONS

We consider the problem of bounding the combinatorial complexity of the lower envelope of n surfaces or surface patches in d-space (d greater than or equal to 3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of the lower envelope of n such surface patches is O(n(d-1+epsilon)), for any epsilon > 0; the constant of proportionality depends on epsilon, on d, on s, the maximum number of intersections among any d-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope is O(n(d-2)lambda(q)(n)) for some constant q depending on the shape and degree of the surfaces (where lambda(q)(n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running time O(n(2+epsilon)), and give several applications of the new bounds.