In this paper, range images edge-based segmentation is investigated. The edge detection in the range images is based on calculating significant change in the angle between surfaces normal by computing the surface normal in 3D for each point in the image. Three methods for computing surface normal based on different Surface Fitting are considered. First one is the Eigenvector Method (EM), and second is the Weighted Least Squares Method (WLSM) which is achieved by combining both Eigenvector and least square methods (LSM), finally the Least Median of Squares method (LMS). These segmentation methods have been applied on 3 test range images of polyhedral objects [1], using Matlab under Linux operating system. Following the process of segmentation, a performance evaluation of the applied segmentation methods is done. Experimental results show that significant performance improvement of range image segmentation by LMS method can be achieved.