Recently, the problem of learning volumetric maps from three-dimensional range data has become quite popular in the context of mobile robotics. One of the key challenges in this context is to reduce the overall amount of data. The smaller the number of data points, however, the fewer information is available to register the scans and to compute a consistent map. In this paper we present a novel approach that estimates global constraints from the data and utilizes these constraints to improve the registration process. In our current system we simultaneously minimize the distance between scans and the distance of edges from planes extracted from the edges to obtain highly accurate three-dimensional models of the environment. Several experiments carried out in simulation as well as with three-dimensional data obtained with a mobile robot in an outdoor environment we show that our approach yields seriously more accurate models compared to a standard approach that does not utilize the global constraints.