Tight numerical bounds for digital terrain modeling by interpolatory subdivision schemes

Surface subdivision schemes are used extensively in scientific and practical applications to generate continuous surfaces in an iterative manner, starting from a set of points. The first subdivision step defines the so called control polygon. This initial polygon can be considered as a very coarse approximation to the final surface. Each iterative step is governed by a local averaging rule which is designed to generate new points by taking some weighted averages of the positions of the neighboring vertices from the previous iteration. If the old vertices (i.e. vertices from the previous iteration) are not to be altered, the subdivision scheme is called an interpolatory subdivision scheme. Some of the most popular interpolatory subdivision schemes are the two point, four point and six point subdivision schemes. These subdivision rules define convergent schemes. The limit surface is continuous and, in some cases, the limit is C1 or C2. This paper is devoted to estimate error bounds between the limit surface and the control polygon defined after k subdivision stages. The results are applied to the case that initial data corresponds with real terrains. The explicit and tight numerical bounds make possible to deal with some basic questions in connection with surfaces that are not defined by analytic formulas. Some previous approaches also give numerical bounds but they are too large to be used for some practical purposes. More precisely, from the numerical results, it is possible to analyze the smoothness of real mountains from a quantitative point of view. These kinds of results are valuable in Cartography because common techniques are based on visual perceptions. A second advantage of the given bounds is that they indicate what approximation scheme is more suitable in order to reconstruct the terrain.