We propose a new randomized incremental approach to visibility update on a terrain model when varying the level of resolution. In particular, we consider visibility update on multiresolution terrain models, which encode surface descriptions at different resolution degrees. Randomized dynamic algorithms for upper envelope of triangles and segments are used for updating the visible image and the horizon, respectively. In this paper, we propose a new randomized dynamic algorithm for upper envelope of triangles, which is an extension of the semi-dynamic algorithm by Boissonnat and Dobrindt. A dynamic algorithm for computing the upper envelope of segments was proposed in a previous paper. It is shown that, under suitable conditions, the update of visibility information by means of these algorithms is more convenient than a complete recomputation.