Mesh segmentation and partitioning of 3D models have always been significant as one of the most structural tools used in many applications of CAD and computer graphics. One of the most versatile of these algorithms, which is capable of optimum segmentation of model, is the iterative algorithm. It is a parametric method based on Lloyd algorithm, which segments the model in an optimized way by plotting the voronoi diagram through the points cloud data. The main disadvantage of this method, which confines its application, is the time-consuming problem. In this paper, employing the nature of fuzzy segmentation, a solution has been proposed to specify the number of regions required for model’s partitioning and to carry out the nonparametric segmentation with no need for user’s initial settings. Additionally, utilizing the approximate voronoi diagram and fuzzy regions construction, a novel method for obtaining the optimized segmentation in a shorter time interval in comparison with other iterative algorithms has been presented. The proposed method has been implemented in a standard model for validation. It has been observed that the obtained results have remarkable improvements relative to the results from the iterative algorithm, which demonstrates the efficiency of this method in segmentation of 3D models.