  Due to the increased rate of information in the present era, local
identification of similar and related data points by using neighborhood
construction algorithms is highly significant for processing information in
various sciences. Geometric methods are especially useful for their accuracy in
locating highly similar neighborhood points using efficient geometric
structures. Geometric methods should be examined for each individual point in
neighborhood data set so that similar groups would be formed. Those algorithms
are not highly accurate for high dimension of data. Due to the important
challenges in data point analysis, we have used geometric method in which the
Apollonius circle is used to achieve high local accuracy with high dimension
data. In this paper, we propose a neighborhood construction algorithm, namely
Neighborhood Construction by Apollonius Region Density (NCARD). In this study,
the neighbors of data points are determined using not only the geometric
structures, but also the density information. Apollonius circle, one of the
state-of-the-art proximity geometry methods, Apollonius circle, is used for
this purpose. For efficient clustering, our algorithm works better with high
dimension of data than the previous methods; it is also able to identify the
local outlier data. We have no prior information about the data in the proposed
algorithm. Moreover, after locating similar data points with Apollonius circle,
we will extract density and relationship among the points, and a unique and
accurate neighborhood is created in this way. The proposed algorithm is more
accurate than the state-of-the-art and well-known algorithms up to almost 8-13%
in real and artificial data sets.
