ALMOST TIGHT UPPER-BOUNDS FOR LOWER ENVELOPES IN HIGHER DIMENSIONS

We consider the problem of bounding the combinatorial complexity of th e lower envelope of n surfaces or surface patches in d-space (d greate r than or equal to 3), all algebraic of constant degree, and bounded b y algebraic surfaces of constant degree. We show that the complexity o f the lower envelope of n such surface patches is O(n(d-1+epsilon)), f or 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 patche s and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conj ecture that the complexity of the envelope is O(n(d-2)lambda(q)(n)) fo r some constant q depending on the shape and degree of the surfaces (w here lambda(q)(n) is the maximum length of (n, q) Davenport-Schinzel s equences). We also present a randomized algorithm for computing the en velope in three dimensions, with expected running time O(n(2+epsilon)) , and give several applications of the new bounds.