The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

Letf ₁, ...,f _m be (partially defined) piecewise linear functions ofd variables whose graphs consist ofn d-simplices altogether. We show that the maximal number ofd-faces comprising the upper envelope (i.e., the pointwise maximum) of these functions isO(n ^d (n)), where(n) denotes the inverse of the Ackermann function, and that this bound is tight in the worst case. If, instead of the upper envelope, we consider any single connected componentC enclosed byn d-simplices (or, more generally, (d – 1)-dimensional compact convex sets) in ^d+1 , then we show that the overall combinatorial complexity of the boundary ofC is at mostO(n ^d+1–(d+1) ) for some fixed constant(d+1)>0.Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development.