Construction of the nearest neighbor embracing graph of a point set

M. Y. Chan (), Danny Z. Chen (), Francis Y. L. Chin () and Cao An Wang ()
Additional contact information
M. Y. Chan: The University of Hong Kong
Danny Z. Chen: University of Notre Dome
Francis Y. L. Chin: The University of Hong Kong
Cao An Wang: Memorial University of Newfoundland

Journal of Combinatorial Optimization, 2006, vol. 11, issue 4, No 7, 435-443

Abstract: 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 $$\Theta(n^2)$$ time in the worst case. We also present an $$O(n \log n + nd)$$ time algorithm, where d is the $$\Omega(\log n)$$ -th largest degree in the utput NNE-graph. The algorithm is optimal when $$d=O(\log n)$$ . The algorithm is also sensitive to the structure of the NNE-graph, for instance when $$d=g \cdot(\log n)$$ , the number of edges in NNE-graph is bounded by $$O(gn \log n)$$ for any value g with $$1 \leq g \leq \frac{n}{\log n}$$ . We finally propose an $$O(n \log n + nd \log d^*)$$ time algorithm for the problem in 3-D, where d and $$d^*$$ are the $$\Omega(\frac{\log n}{\log \log n})$$ -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 $$d^*$$ is $$O(\frac{\log n}{\log \log n})$$ .

Keywords: Computational geometry; Nearest neighbors; Network connections (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-8459-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:11:y:2006:i:4:d:10.1007_s10878-006-8459-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-8459-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().