In this paper, we present an algorithm for multivariate interpolation of scattered data sets lying in convex domains [Formula: see text], for any [Formula: see text]. To organize the points in a multidimensional space, we build a [Formula: see text]-tree space-partitioning data structure, which is used to efficiently apply a partition of unity interpolant. This global scheme is combined with local radial basis function (RBF) approximants and compactly supported weight functions. A detailed description of the algorithm for convex domains and a complexity analysis of the computational procedures are also considered. Several numerical experiments show the performances of the interpolation algorithm on various sets of Halton data points contained in [Formula: see text], where [Formula: see text] can be any convex domain, like a 2D polygon or a 3D polyhedron. Finally, an application to topographical data contained in a pentagonal domain is presented.