Region-based coding schemes may yield considerable improvements in performance as compared to block-based schemes. A fundamental problem in region-based coding is to efficiently encode the interior of each region. This paper proposes two approaches for coding the interiors of arbitrarily-shaped regions. The first is an adaptive iterative scheme and the second is a matching pursuits-type scheme. A geometric interpretation of the problem is given to provide insight into these approaches and to compare their different properties and performances. A number of examples illustrate the performance of the previous and proposed approaches.