This paper presents a new data reduction algorithm to reduce redundant in rang image or three dimension point cloud. Firstly, an automatic subdivision program is developed to identify the most representative data points among redundant points. The subdivision program employs the standard k-means clustering procedure to gather the similar data points together in spatial domain and uses the max normal deviation to minimize the dissimilarity in feature field. Secondly, an automatic boundary detection algorithm is developed to maintain the integrity of the border, which is conducted before the subdivision program. To avoid the final distribution of sampled points locally greedy and unbalanced, a refinement algorithm is proposed, which runs after the subdivision program. The effectiveness of the proposed k-means clustering data reduction algorithm is demonstrated through the simplification results of the practical range image and three dimension point cloud.