A method is proposed for the determination of a progressive polyhedral approximation of 3-D digitized surfaces whose points are located on a regular lattice. It relies on an iterative and adaptative splitting of the triangular faces of an initial polyhedral surface. Assuming a bijection between the digitized surface and its approximation, a partition of the data base is operated. The algorithm allows for the measurement of the local quality of the approximation and avoids the generation of ill-defined triangles with sharp corners. Its low computational complexity permits the approximation of very large sets of points (hundreds of thousands).