Surface shape description from 3-D measurements is an important problem since many applications, including recognition and scene interpretation, rely on this initial description. In order to be reliable, the recovered description must not be sensitive to the acquisition conditions: (1) it must be robust in the presence of spurious measurements, (2) it must be viewpoint invariant, and (3) the density of measurements must be sufficient for stability. Very few reconstruction approaches based on regularization, segmentation, or geometric primitive extraction respect one or even two of these three conditions. A new reconstruction approach is presented for which a polynomial-based description of surface sections is provided to higher level applications as reliable hypotheses. The first two conditions are met by including a measurement error model as an integral part of the recovery procedure. To meet the third condition, a test of the stability of the hypothesized model is performed in the measurement space and states whether the hypothesis is data-dependent or not by searching for the redundancy in the data supporting the model. Along with the set of descriptive parameters for each polynomial section, a figure of merit based on the covariance matrix of the parameters is computed. The validity of the reconstruction approach is demonstrated by extracting planar and quadric sections from range data through an implementation on a massively parallel SIMD processor architecture.