An efficient method is proposed to construct the six-dimensional Potential Energy Surface (PES) for diatomic molecule-surface interactions from low dimensional cuts obtained in ab initio calculations. The efficiency of our method results from a corrugation-reducing procedure based on the observation that most of the corrugation in a molecule-surface PES is already embedded in the atom-surface interactions. Hence, substraction of the latter leads to a much smoother function which makes accurate interpolations possible. The proposed method is a general one and can be implemented in a systematic way for any system. Its efficiency is illustrated for the case of H-2/Pd(111) by using recent ab initio data. We report also the results of very stringent checks against ab initio calculations not used in the interpolation. These checks show the high accuracy of our method.