## 1 Introduction  
With the popularity of 3D scanning measurement technology, the acquisition of large-scale scattered point cloud (LSSPC) is easier due to the high resolution of the scanning devices. However, the point based model must be processed for rendering, feature recognition, smoothing, sampling, and surface reconstruction to meet the requirements of the application. The normal vector estimation is actually the basis of point cloud editing, while the efficiency barely meets the great demand of the application. Many algorithms aim to estimate the normal vectors of the scattered point cloud. The Euclidean nearest neighbor (ENN)-based methods are the most popular algorithms due to their simplicity [1, 2]. [PERSON] [3] presented a fast and quality estimator based on a neighborhood shift to estimate the normal vector accurately. [PERSON] and [PERSON] [4] realized 3D point cloud cluster analysis using the Principal Component Analysis (PCA) of normal vector distribution that depends on a neighbor. [PERSON] and [PERSON] [5] developed a method based on fitted directional tangent vectors using a local voronoi mesh, which needs to identify the neighboring points first. [PERSON] [6] focused on finding balanced neighbors using an Elliptic Gabriel graph (EGG) algorithm, followed by local quadratic surface fitting methods for the normal vector estimation of each point. [PERSON] [7] reported a low-rank subspace clustering algorithm to estimate the normal vector robustly, while the method had to distinguish whether the points belonged to smooth regions and calculate the normal vector for them before clustering. The calculation of normal vectors based on ENN usually performs the following steps: First, sort the scattered point cloud into a classic data structure, such as a k-d tree [8] or hash table; then, search the nearest neighbor within a fixed quantity or a fixed distance of each point; at last, compute the normal vector using neighbor points for each point. Although these ENN-based methods are widely used, there are some difficulties to overcome [9; 10]. On one hand, the ENN is generally determined by a predefined constant or a spherical space with a specific radius. The reasonable neighborhood range is crucial for accurate and reliable normal vector estimation, especially when dealing with LSSPC [11]. On the other hand, these ENN-based algorithms are perhaps reasonable in the distance but are not reasonable in spatial distribution [12]. When the point distribution is uneven, the distance-based method gives obviously unbalanced neighbors, which result in unreliable normal vector estimation results. [PERSON] [6] and [PERSON] [13] discussed the EGG algorithm that was used to overcome this shortcoming, but this EGG algorithm does not consider the situation that the point is located at the edge of the surface. Some researchers use the triangle mesh to calculate the normal vector for the point cloud. [PERSON] [14] introduced a new normal vector estimation method based on the matching results of the local Delaunay triangle mesh formed at each point. The normal vectors of the triangular meshes that contain the given point were recorded by local searching at first; then, the average of these normal vectors was calculated as the normal vector of the point. [PERSON] and [PERSON] [15] used the centered weights to approximate normal vectors. However, different triangulation results may lead to different normal vector calculation results due to the ambiguity when converting the point cloud to triangulation. Either the ENN-based methods or the triangle-based algorithms--whichever is the nearest neighbor for each point--needs to be found. This means huge times of power operation, open square operation, and comparison operation are involved in neighbor searching. It is a very time-consuming process [16; 17], especially when dealing with large-scale scattered point cloud.