Segmentation of point-cloud is still a challenging problem, regarding observation noise and various constraints defined by applications. These difficulties do not concede to its necessity for almost all kinds of modeling approaches using point-cloud. However, the criteria to justify the quality of a clustering result are not much studied. In this paper, we first propose a point-cloud segmentation algorithm using adapted k-means to cluster normal vectors obtained from tensor voting. Then we concentrate on how to use a non-parametrical criterion to validate the clustering results, which is an approximation of the information introduced by the clustering process. Compared with other approaches, we use noisy point-cloud obtained from moving laser range finders directly, instead of reconstruction of 3d grid-cells or meshing. Moreover, the criterion does not rely on the assumption of distributions of points. We show the distinguishable characteristics using the proposed criteria, as well as the better performance of the novel clustering algorithm against other approaches. © 2013 IEEE.