Let F be a collection of bivariate continuous functions of constant complexity, which changes dynamically by insertions and deletions of functions. We present a technique for dynamically maintaining the lower envelope of F, so that we can efficiently retrieve the function attaining the envelope at any query point q∈R2. Our data structure answers queries and performs updates in polylogarithmic time per operation, improving an earlier technique of Agarwal, Efrat, and Sharir. The main tool in our analysis are vertical shallow cuttings, a refined variant of the notion of shallow cuttings, as introduced by Matoušek in his seminal 1992 paper on reporting points in halfspaces. In our variant, the cells of the cutting are vertical semi-unbounded (pseudo-)prisms, whose union covers the first k levels of the arrangement of F. Vertical shallow cuttings have already been considered by Chan and others, but our version has additional properties: The ``celinigs'' of the prisms form an xy-monotone terrain, which approximates the k -level up to any prespecified relative error. The construction of such a vertical shallow cutting for arrangements of planes is simpler, and its construction simplifies and improves earlier approaches. A special instance of the dynamic lower envelope problem is the dynamic maintenance of the convex hull of a point set in R3 ; it is dual to the dynamic maintenance of the lower envelope of planes. We re-examine the best known technique for doing this, due to Chan, and manage to improve the cost of a deletion (the costliest operation in his scheme) to O(log5n) (from O(log6n) ), while keeping the cost of insertions and queries unchanged. Our scheme has many applications. For example, we get efficient schemes for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions that includes Lp -norms and additively weighted Euclidean distances, and for general (convex, pairwise disjoint) sites that have constant description complexity (line segments, disks, etc.). The polylogarithmic update and query time of our data structure improves the earlier data structure of Agarwal, Efrat and Sharir that required O(nε) time for an update and O(logn) time for a query. Our data structure has numerous other applications, and in all of them it gives faster algorithms, typically reducing an O(nε) factor in the bounds to polylogarithmic. Joint works with Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty and Paul Seiferth.