Construction of the nearest neighbor embracing graph of a point set |
| |
Authors: | M Y Chan Danny Z Chen Francis Y L Chin Cao An Wang |
| |
Institution: | (1) Department of Computer Science and Information Systems, The University of Hong Kong, Hong Kong;(2) Department of Computer Science and Engineering, University of Notre Dome, Notre Dome, IN 46556, USA;(3) Department of Computer Science, Memorial University of Newfoundland, St. John’s, Newfoundland, Canada |
| |
Abstract: | This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given point
set V of size n in the k-dimensional space (k-D) for k = 2,3. The NNE-graph provides another way of connecting points in a communication network, which has lower expected degree
at each point and shorter total length of connections with respect to those using Delaunay triangulation. In fact, the NNE-graph
can also be used as a tool to test whether a point set is randomly generated or has some particular properties.
We show that in 2-D the NNE-graph can be constructed in optimal
time in the worst case. We also present an
time algorithm, where d is the
-th largest degree in the utput NNE-graph. The algorithm is optimal when
. The algorithm is also sensitive to the structure of the NNE-graph, for instance when
, the number of edges in NNE-graph is bounded by
for any value g with
. We finally propose an
time algorithm for the problem in 3-D, where d and
are the
-th largest vertex degree and the largest vertex degree in the NNE-graph, respectively. The algorithm is optimal when the
largest vertex degree of the NNE-graph
is
. |
| |
Keywords: | Computational geometry Nearest neighbors Network connections |
本文献已被 SpringerLink 等数据库收录! |
|