Abstract—This paper concerns the creation of efficient surface representations from laser point clouds. We produce a continuous, implicit, non-parametric representation with an update time that is constant. The algorithm places no restriction on the complexity of the underlying workspace surfaces and automatically prunes redundant data via an information theoretic criterion. This criterion makes the use of GP 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 level and reconstruction error. We attain decimation factors in excess of two orders of magnitude without significant degradation in fidelity.