Selective refinement is an operation acting on multiresolution surface models, aimed to provide a mesh approximation with a resolution variable over the surface. We address some effciency issues related to selective refinement, and we present some results on data structures and algorithms that work on a multiresolution triangle-based model, called a Multi-Triangulation. In particular, we analyze the trade-off between storage costs of data structures, and computational effciency of algorithms they can support; and we propose algorithms for variants of selective refinement, combined with some spatial queries of interest in the applications.