Abstract – This paper concerns the creation of efficient surface representations from laser point clouds created by a push broom laser system. We produce a continuous, implicit, non-parametric and non-stationary representation with an update time that is constant. This allows us to form predictions of the underlying workspace surfaces at arbitrary locations and densities. The algorithm places no restriction on the complexity of the surfaces and automatically prunes redundant data via an information theoretic criterion. This criterion makes the use of Gaussian Process Regression a natural choice. We adopt a formulation which handles the typical non-functional relation between XY location and elevation allowing us to map arbitrary environments. Results are presented that use real and synthetic data to analyse the trade-off between compression rate and reconstruction error. We attain decimation factors in excess of two orders of magnitude without significant degradation in fidelity.