We propose a new distance measure between 2-dimensional points to provide a total order for an entire point set and to reflect the correct geometric meaning of the naturalness of the point ordering. In general, there is no total order for 2-dimensional point sets, so curve reconstruction algorithms do not solve the self-intersection problem because the distance used in the previous methods is the Euclidean distance. A natural distance based on Brownian motion was previously proposed to solve the self-intersection problem. However, the distance reflects the wrong geometric meaning of the naturalness. In this paper, we correct the disadvantage of the natural distance by introducing a polar-natural distance, and we also propose a new curve reconstruction algorithm that is based on the polar-natural distance. Our experiments show that the new distance adequately reflects the correct geometric meaning, so non-simple curve reconstruction can be solved. The problems of reconstructing a shape from sample points appear in many scientific and engineering applications. Because of its practical importance, many algorithms have been proposed over the last two decades in the fields such as the reverse engineering of geometric models and image processing of medical images. Especially, curve reconstruction plays an important role in the shape reconstruction problems because most of boundaries of shapes are represented by the set of curves. Curve reconstruction is the problem of computing a piecewise linear approximation to a curve from a set of sample points. So curve reconstruction consists of two steps: the first step is how to order the given points and the second step is how to interpolate the ordered points [1] - [4] . The first step is called the point ordering problem . Many approaches have been suggested for the point ordering problem. Edelsbrunner et al. [5] defined the α-shapes of point sets as the underlying space of a simplicial complex. Attali proposed the r -regular shape method, where the r -regular shapes are characterized by requiring that any circle passing the points on the boundary has radius greater than r [6] . These methods deal with only uniform sample points. For the non-uniform sample points, Amenta et al. [7] proposed the first algorithm to reconstruct a curve from non-uniform sample points with guarantee. This algorithm uses the Voronoi diagram and the Delaunay triangulation of the sample points. Dey et al. [8] proposed the nearest neighbor approach based on the properties of Voronoi diagrams. These algorithms work only under the assumption that the sample points are dense and do not work for non-simple curve reconstruction because they reconstruct curves without the consideration of curve's orientation [9] - [12] . Kim et al. [3] proposed a point ordering approach with a natural distance to reflect the orientation. The natural distance is based on properties of Brownian motion so that the approach enables us to give 1-dimentional order to points on 2-dimentional space. However, the approach missed important geometric property: the right direction of Brownian motion. In this paper, we introduce a new natural distance based on polar coordinates so that the distance enables our algorithm to reflect the direction properly and resolve the non-simple curve reconstruction. In this section, we review the properties of Brownian motion and the natural distance [3] . First of all, we will discuss naturalness for a direction-based distance. In order to do this, we define the naturalness for a distance between points which is suitable to order the points on a 2D plane. For chosen consecutive points p _i-1 and p_i which are already ordered, we define the ordering direction vector as vector . For the ordering direction, what will be the next point p _i+1 ? Let P be the sample point sets. We define the candidate set C _i+1 ( r_i ) for the next point p _i+1 as as shown in Fig. 1 , where d ( p , q ) is the Euclidean distance between p and q , and r_i is the radius of the ordering neighborhood. The radius r_i is computed by the average length of the consecutive points: If a measure μ prefers to pick up the next point q ∈ C _i+1 satisfying the following conditions, then we say that the measure has a naturalness and call it as a natural distance : (C-1) Suppose p_i and q ₁ , q ₂ ,⋯ , q_m ∈ C _i+1 are on the same line. Then the measure prefers to choose the closest one q_k to the previous point p_i among q_j ’s : (C-2) Suppose q ₁ , q ₂ ,⋯ q_m ∈ C _i+1 are on the same circle with center p_i , and the angle between is strictly smaller than the angle between . Then q_k is more preferable to p_j : The condition (C-2) implies that, among the points with the same Euclidian distance from p_i , we want to choose the point which makes the arc, made by connecting the chosen points, most smooth as shown in Fig. 2 . To show the naturalness of distance, we adopt a simple property of one dimensional Brownian motion. An easier way to understand Brownian motion is to think of it as a continuous version of the random walk process. As documented in an enormous amount of literature on stochastic processes such as [17], [18], Brownian motion has several properties which explain the irregular motion observed in nature; for example, in two-dimensional space the motion of pollen grains suspended in liquid which does not flow. Among those, we use only the following property throughout this paper: (P.B) For given time T, Brownian motion starting at 0 is a random variable normally distributed with mean 0 and variance T. Roughly speaking, (P.B) means that the set of original points on the real line at time 0, which move randomly, become the set which is normally distributed with mean 0 and variance T after T time. Now, we will introduce the polar-natural distance function by understanding the right geometric meaning of the Brownian property. We assume that p _i-1 and p_i are already chosen and q is an arbitrary point in C _i+1 . In order to determine the next point p _i+1 , Kim et al. [3] defined the natural distance in the following manner. They applied a 2-dimension transformation so that p _i-1 is on the negative x -axis and p_i is the origin of R ² . In order to help the geometric understanding, let R ( p _i-1 , p_i ) be the ray with the initial point p_i and the directional vector and L ( q , p _i-1 , p_i ) be the perpendicular line to R ( p _i-1 , p_i ) passing through the point q satisfying (C-1) as shown in Fig. 3 . Therefore, the arbitrary point q can be represented by the new coordinates q = ( q_t , q_s ) as follows: where The coordinate q_t is the Euclidian distance between p_i and the intersection of R ( p _i-1 , p_i ) and L (q, p _i-1 , p_i ), and the coordinate q_s is the signed Euclidian distance between q and the intersection of R ( p _i-1 , p_i ) and L ( q , p _i-1 , p_i ). Then we can think the pair ( q_t , q_s ) as the new coordinates of q . With the property (P.B) of Brownian motion, we further think of the q_t -axis as the time axis with the original point p_i , and q_s -axis as the axis representing the value of Brownian motion. Therefore, if q_t > 0, q_s is considered as a sample point of the random variable which has the normal distribution with mean 0 and variance q _t as shown in Fig. 4 , then we consider the point q as one of the normally distributed points after q _t time, which is randomly diffused from the original point. The value of distribution cannot directly be applied to the natural distance because the distribution changes according to the position of q . So we transform the distribution into the standard normal distribution so that the random variable q_s is transformed to the standard random variable . It is well known that the larger the value of the standard random variable is, the smaller the probability is. Therefore, the problem of determining the next point p _i+1 is transformed into that of computing the minimum of the standard random variables. Kim et al. [3] defined a natural distance by the following manner: where K is a constant and plays a role of a subjective weight. It is well known that the natural distance of Kim et al. [3] marked a turning point in the research on point ordering problem. Most of the distances used in the previous point ordering research cannot give a total order to the set of points on R ² , whereas the natural distance can do that. So we could solve the problem of reconstructing curves having self-intersections. However, there are obvious shortcomings in the natural distance. The first is that the random variable used in the natural distance cannot reflect the right geometric meaning of the conditions (C-1) and (C-2. The second is that the result of point ordering is very sensitive to the value of subjective weight. The condition (C-1) shows that all points on the same line with p_i have the same value q_s , the condition (C-2) shows that all points on the same circle with center p_i have the same value q_t . So the random variable cannot resemble the right geometric meaning of conditions. In this paper, we introduce a new natural distance which may give a total order to two-dimensional points and reflect the right geometric meaning of conditions (C-1) and (C-2). First of all, we define the polar-natural coordinates as ( r_i ( q ), θ_i ( q )), where . By using this coordinates and understanding the geometric meaning as shown in Fig. 5 , we define the polar-natural distance as In this section, we will describe a practical algorithm for ordering points in an unorganized point cloud. Assume that there are arbitrarily scattered n points, called sample points, in R ² . Denote the set of all sample points by P. The point ordering problem aims to choose a subset SP of P , where SP is a well-ordered set satisfying the natural conditions (C-1) and (C-2) mentioned in Section 2. In the above theoretical section, we have assumed that the first point p ₁ and the second point p ₂ are known. This easily enabled us to initialize the algorithm at the first point with an initial direction . In general, the result of the point ordering problem is dependent on the initial direction. But, in practice, p ₁ and p ₂ are not known. Moreover, the well-ordered subset SP may have several connected components, and may be open or closed according to the distribution of the data points. So we need to analyze the distribution of the sample points in order to find out the property of the subset SP . In general, the sample points of the unorganized point cloud for curve reconstruction may cluster in several groups and the points of each group are densely located near meaningful trajectories. So, the shape of each cluster looks like the union of bands. The objective of our algorithm is to remove outliers in each cluster and find out a well-ordered subset that plays a role of skeletons of clusters. Our algorithm consists of three major steps: data clustering, determination of the initial direction, and local point ordering. Most partitioning methods cluster objects based on the Euclidean distance between objects. Such methods can find only spherical-shaped clusters and encounter difficulty at discovering clusters of arbitrary shapes. We cannot apply such clustering methods directly to our problem because the shape of the input point set P is unknown. In this paper, we adopt the DBSCAN clustering algorithm based on the density, which is useful to filter out outliers and discover clusters of an arbitrary shape. The general idea is to continue growing the given cluster as long as the density in the neighborhood exceeds some threshold; that is, for each data point within a given cluster, the neighborhood of a given radius cr , called clustering radius has to contain at least a minimum number of points. By exploiting DBSCAN algorithm, we may obtain nc clusters CL ¹ CL ² ,…, CL^nc , in P of a band-like shape. For each cluster CL^j , we choose a point which may well represent the character of the shape of the cluster as the initial point, denoted by cp^j . Now, we will try to determine the initial direction of the natural distance at the initial point cp^j for each cluster CL^j . For the sake of convenience, we set the initial point as p ₁ . In order to analyze the distribution of points near p ₁ , we compute the neighborhood N ( p ₁ , r ) of p ₁ with a given radius r, called ordering radius ; N ( p ₁ , r ) = { p ∈ CL^j | pd ( p ₁ , p ) ≤ r }, where pd ( p , q ) is the Polar-Natural distance between two points pand q, which is defined in Section 2. And then we apply the PCA (Principal Components Analysis) to the neighborhood because the principal component analysis of a set of points gives us the mean, an orthogonal frame, and the standard deviation of the neighbors. Let q ₁ , q ₂ ,⋯, q_m be the points in the neighborhood N ( p ₁ , r ). We compute the mean m of the neighbors such that and then we construct the covariance matrix We compute the eigenvector of the covariance matrix which corresponds to the maximal eigenvalue so that it plays a role of the major principal axis in the neighborhood. Let be the unit vector on the principal axis. Then the neighborhood N ( p ₁ , r ) may be subdivided into two half discs: Where If HD _– = ø or HD ₊ = ø, then the point p ₁ is one of the two end points of SP. Otherwise the point is a middle point of SP so that we should apply the following one-way ordering algorithm to both HD ₊ and HD _– with the direction vectors , respectively. Let SP ₊ and SP _– be the solutions of the one-way ordering problem with the initial directions , respectively. Then the solution SP of the original point ordering problem may be obtained by merging the subsets SP ₊ and SP _– , i.e., SP = SP ₊ ∪ SP _– . Now, we are ready to explain the one-way point ordering algorithm with the first point p ₁ and the initial direction . First of all, we have to select the candidates of the next point p ₂ in the neighborhood N ( p ₁ , r ). It is well known that the candidate C ₂ set is the same as the half disc HD ₊ ( p ₁ , r ). So, without loss of generality, we may put C _i+1 = HD ( p ₁ , r ). Next, we select the second point p ₂ in N ( p ₁ , r ) satisfying the following condition: f ₁ ( p ₁ ) = min _p∈HD+(p1) f ₁ ( p ), where the function f ₁ ( p ) is derived from the initial direction vector . We have known that the above condition satisfies the properties of conditions (C. 1) and (C. 2). Then the point p ₂ is added to the well-ordered set so that SP ₊ = { p ₁ , p ₂ }. In order to find out the third point p ₃ we compute the candidate set C ₃ that is the half disc HD ₊ ( p ₂ , r ) with the direction vector . The third point p ₃ should satisfy the following condition: f ₂ ( p ₂ ) = min _p∈HD+(p2) f ₂ ( p ), where the function f ₂ ( p ) is derived from the direction vector . Then SP ₊ = { p ₁ , p ₂ , p ₃ }. We apply the above process until the candidate set C _i+1 is empty or the intersection of C _i+1 and HD _– ( p ₁ ) is not empty. When the algorithm meets the former condition, it generates one of the two end points for an open curve, so it has to be applied to the other region of the cluster with the direction . If the latter is satisfied, then the new obtained point p _n1 is near the first point p ₁ .We can consider the well-ordered set is a closed piecewise curve so that there is no need to continue this one-way point ordering algorithm in the cluster. The solution of the one-way point ordering problem is SP ₊ = { p ₁ , p ₂ , ⋯ , p _n1 }. By similar process, we may get SP _– = { p _-n2 , p _-n2+1 , ⋯ , p _-1 } as the solution of the backward one-way ordering algorithm. Now, we may obtain the first connected well-ordered subset SP = SP ₊ ∪ SP _– . Therefore, the global point ordering problem can be solved by applying the above process to all of clusters in P. The outline of our natural point ordering algorithm is as follows. The three major steps of this algorithm are to partition the point set P into several clusters, to find out the neighbor points in N ( p , r ), and to select one point who has the minimum natural distance among them. The computational complexity of DBSCAN algorithm is O ( n log n ), where n is the number of the input cloud points. It is well-known that the algorithm is sensitive to the user-defined parameters. The second process of this algorithm runs in O ( n ) time. The process is to find out a neighborhood N ( p , r ) of a given point p and to apply the principal component analysis to the neighborhood in order to derive the initial direction. The third process is repeatedly to find out a candidate set C _i+1 , and to select one point who has the minimum natural distance among the candidates. It takes O ( kM ), where k is the number of the output points in SP and . Our algorithm is output-sensitive. However, in the worst case, the total time complexity of this algorithm may be O( n ² ), where the most of candidate sets have only one point as neighbors. Our experimental results demonstrate the superiority of our point ordering algorithm based on the polar-natural distance. First of all, we compare the results of curve reconstruction for a sampled point set which are obtained by the natural distance and by the polar-natural distance. The point set is obtained by sampling from points on two circles with different radius. Figure 6 presents two piecewise linear curves obtained by the natural point ordering method (a) and the polar-natural ordering method (b). These figures show quite different curves. The curve generated by our distance is more natural than that by the natural distance in [3] . Moreover, the polar-natural poing ordering method can be used to reconstruct a curve for the sample points set containing the noise points not on the curve as well as those on it. Fig. 7 shows the results of curve reconstruction for a point cloud set. The cloud poing set was obtained by mouse dragging-and-dropping so that the global figure of the set has several self-intersections. Fig. 7 (a) does not overcome the self-intersection problem, whereas Fig. 7 (b) well reflects the global configuration of the data set. Fig. 8 shows the process of our polar-natrual point ordering algorithm. Fig. 8 (a) is the initial point set. The set was obtained by mouse dragging-and-dropping so that the global figure of the set is the union of two ‘C’-type point sets. Fig. 8 (b) shows the middle state which has two curves. Each curve has two components SP ₊ and SP _– . The final result (c) has two curves. Since our algorithm has a special key that is polar-natural distance it can solve the self-intersection problem. Therefore our algorithm can be applied to non-simple curve reconstruction. In this paper, we proposed an improved curve reconstruction algorithm by exploiting a new distance. We already introduced a natural distance in [3] which is based on a useful property of Brownian motion. The distance enables us to provide a totally order for the set of arbitrarily scattered points. However, the work of [3] missed the geometric meaning of the naturalness conditions (C-1) and (C-2). In this paper we proposed the polar-natural distance that is based on the polar coordinates. The totally ordered set generated by the polar-natural distance is more natural than that by the natural distance. By connecting these ordered points, we can obtain desired or meaningful curves. Also the polar-natural point ordering method can be used in the reconstruction of smooth curves, even though the data set contains noise points. The several experimental results show the superiority of our point ordering algorithm based on the polar-natural distance. Hyoung-Seok Kim He received the M.S. and Ph.D. degrees in department of Mathematics from KAIST (Korea Advanced Institute of Science and Technology) in 1992 and 1998, respectively. During 1998-1999, he worked at ETRI as a post-Doctorial researcher. He is a professor in dept. of Multimedia Engineering at Dong-Eui University from 1999. His interesting research fields are computer graphics, computer game engine, and applied mathematics. Ho-Sook Kim She received the M.S. and Ph.D. degrees in department of Computer Engineering from Ewha Womans University in 1999 and 2005, respectively. She was an associate professor in division of Advance Computer Information at Dong-Eui Institute of Technology from 2001 to 2009. She is a teacher in dept. of mathematics and computer science at Korea Science Academy of KAIST from 2010. Her interesting research fields are database, data mining, GIS, and mobile technology.