In this dissertation, we consider the problem of piecewise polynomial approximation of functions over sets of triangulations. Recently developed adaptive methods, where the hierarchy of triangulations is not fixed in advance and depends on the local properties of the function, have received considerable attention. The quick development of these adaptive methods has been due to the discovery of the wavelet transform in the 1960's, probably the best tool for image coding. Since the mid 80's, there have been many attempts to design `Second Generation' adaptive techniques that particularly take into account the geometry of edge singularities of an image. But it turned out that almost none of the proposed `Second Generation' approaches are competitive with wavelet coding. Nevertheless, there are instances that show deficiencies in the wavelet algorithms. The method suggested in this dissertation incorporates the geometric properties of convex sets in the construction of adaptive triangulations of an image. The proposed algorithm provides a nearly optimal order of approximation for cartoon images of convex sets, and is based on the idea that the location of the centroid of certain types of domains provides a sufficient amount of information to construct a 'good' approximation of the boundaries of those domains. Along with the theoretical analysis of the algorithm, a Matlab code has been developed and implemented on some simple cartoon images.
adaptive approximation, triangulation, image compression