Cross-borehole tomography suffers from a well-known problem of data incompleteness: the limited ray coverage dictated by the poor experimental geometry implies that certain features of the velocity field are not determined by the data. Construction of a tomographic image of the velocity field therefore requires the addition of prior constraints to the inversion. In the Fourier wavenumber domain (assuming straight-line rays), the process of adding prior constraints is equivalent to specifying unmeasured wavenumber coefficients. The projection onto convex sets (POCS) algorithm can impose physically plausible constraints that allow high quality tomographic images to be produced. Each constraint is viewed as defining a set (in function space) of images that satisfy that particular constraint. The POCS method finds one or more images in the intersection of the constraining sets, which is equivalent to finding an image that simultaneously satisfies a number of constraints including the observed data. The sets of images that we employ include: those that satisfy the data in the sense of having certain known wavenumber components, those that have bounded energy in certain unmeasured wavenumber components, those that have seismic velocity bounded everywhere (e.g., nonnegative), and those in which the velocity structure is confined to the region between the boreholes. An advantage of the POCS algorithm is that it allows both space-domain and wavenumber-domain constraints to be imposed simultaneously. In our implementation of the POCS algorithm, we make use of the fast Fourier transform to rapidly iterate between the space and Fourier-wavenumber domains. We test the method on synthetic data, and show that it significantly reduces the artifacts in the image, when compared to other methods. We then apply it to data from a cross-borehole experiment in Manitoba, Canada, that were previously studied by others. We achieve a tomographic image of the velocity field that is similar in many respects to the results of others, but which possesses fewer artifacts.