Synthesizing new views from existing ones is an emerging field with various applications. Approaches for view synthesis rely upon dense or sparse matching between existing views. In all cases, some parts of the original images are inevitably unmatched and, therefore, the synthesis of new views of the corresponding regions need to rely upon sparse sets of matched points. Triangulation based upon sparsely matched points constitutes a possible solution for the handling of unmatched regions. However, such a triangulation should respect the underlying geometry of the corresponding scene. In this paper, a novel approach is proposed for a physically valid joint-triangulation of sparsely matched points. The proposed approach is based upon the maximization of a physical validity criterion which is supported by textured regions in the images. The produced triangulation is such that each triangle corresponds approximately to a planar surface in the scene. Given an arbitrary initial triangulation, the proposed approach refines it by modifying links between vertices so as to locally increase the physical validity measure. Furthermore, since missing or incorrect matched points may impede the correctness of the current triangulation, an iterative split-and-merge phase adds or removes matching points in low-score triangles, by means of a correctness evaluation based upon a large evaluation support. The paper presents results of the proposed approach with synthetic views—which allow quantitative performance evaluation—and natural images.