The problem of range image segmentation is considered, and the relative performance of combinations of several differential geometric features such as the orientation and tilt angles of the normal, Gaussian curvature, and mean curvature is evaluated. A very fast and simple histogram-based segmentation scheme for polyhedral objects and reliable segmentation methods based on modified K-means and Unsupervised Fuzzy Partition-Optimum Number of Clusters (UFP-ONC) algorithms are presented. These methods are computationally and implementationally simple, work for both polyhedral and curved objects, are robust enough to deal with noisy features, and perform well without any knowledge of the type and number of objects present. Modifications to the K-means and UFP-ONC algorithms are necessary to deal with periodic features such as the orientation angle of the normal. The combination of orientation angle and mean curvature is shown to produce the best results, and the modified UFP-ONC algorithm is shown to perform better in terms of detecting more meaningful clusters, picking the optimum number of clusters and handling noisy data. Experimental results on range images obtained from the Environmental Research Institute of Michigan illustrate that the proposed methods are effective.