NEW BOUNDS FOR LOWER ENVELOPES IN 3 DIMENSIONS, WITH APPLICATIONS TO VISIBILITY IN TERRAINS

We consider the problem of bounding the complexity of the lower envelo pe of n surface patches in 3-space, all algebraic of constant maximum degree, and bounded by algebraic arcs of constant maximum degree, with the additional property that the interiors of any triple of these sur faces intersect in at most two points. We show that the number of vert ices on the lower envelope n such surface patches is O(n(2).2(c root l ogn)), for some constant c depending on the shape and degree of the su rface patches. We apply this result to obtain an upper bound on the co mbinatorial complexity of the ''lower envelope'' of the space of all r ays in 3-space that lie above a given polyhedral terrain K with n edge s. This envelope consists of all rays that touch the terrain (but othe rwise lie above it). We show that the combinatorial complexity of this ray-envelope is O(n(3).2(c root logn)) for some constant c; in partic ular, there are at most that many rays that pass above the terrain and touch it in four edges. This bound, combined with the analysis of de Berg et al. [4], gives an upper bound (which is almost tight in the wo rst case) on the number of topologically different orthographic views of such a terrain.