In this paper we present an efficient technique tolearn Associative Markov Networks (AMNs) for the segmentation of 3D scan data. Our technique is an extension of the work recently presented by Anguelov et al. [1], in which AMNs are applied and the learning is done using max-margin optimization. In this paper we show that by adaptively reducing the training data, the training process can be performed much more efficiently while still achieving good classification results. The reduction is obtained by utilizing kd-trees and pruning them appropriately. Our algorithm does not require any additional parameters and yields an abstraction of the training data. In experiments with real data collected from a mobile outdoor robot we demonstrate that our approach yields accurate segmentations.