There are no files associated with this item.

##### Supplementary
• Appears in Collections:

#### Article: Construction of the nearest neighbor embracing graph of a point set

Title Construction of the nearest neighbor embracing graph of a point set Chan, MYChen, DChin, FYLWang, CA 2004 Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3111, p. 150-160 How to Cite? This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given set of points 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 than Delaunay graph. 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 in 2-D that the NNE-graph can be constructed in optimal O(n2) time in the worst case. We also present an O(n log n + nd) algorithm, where d is the Ω(log n)th largest degree in the output 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 · (log n), the number of edges in NNE-graph is bounded by O(gn log n) for 1 ≤ g ≤ n/log n. We finally propose an O(n log n + nd log d*) algorithm for the problem in 3-D, where d and d* are the Ω(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(log n/log log n). © Springer-Verlag Berlin Heidelberg 2004. http://hdl.handle.net/10722/89149 0302-97432005 Impact Factor: 0.4022015 SCImago Journal Rankings: 0.252 References in Scopus

DC FieldValueLanguage
dc.contributor.authorChan, MYen_HK
dc.contributor.authorChen, Den_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorWang, CAen_HK
dc.date.accessioned2010-09-06T09:52:59Z-
dc.date.available2010-09-06T09:52:59Z-
dc.date.issued2004en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3111, p. 150-160en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89149-
dc.description.abstractThis paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given set of points 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 than Delaunay graph. 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 in 2-D that the NNE-graph can be constructed in optimal O(n2) time in the worst case. We also present an O(n log n + nd) algorithm, where d is the Ω(log n)th largest degree in the output 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 · (log n), the number of edges in NNE-graph is bounded by O(gn log n) for 1 ≤ g ≤ n/log n. We finally propose an O(n log n + nd log d*) algorithm for the problem in 3-D, where d and d* are the Ω(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(log n/log log n). © Springer-Verlag Berlin Heidelberg 2004.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleConstruction of the nearest neighbor embracing graph of a point seten_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1382-6905&volume=11&issue=4&spage=435 &epage= 443&date=2006&atitle=Construction+of+the+Nearest+Neighbor+Embracing+Graph+of+a+Point+Seten_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.scopuseid_2-s2.0-35048843791en_HK
dc.identifier.hkuros117583en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048843791&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3111en_HK
dc.identifier.spage150en_HK
dc.identifier.epage160en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, MY=7402597863en_HK
dc.identifier.scopusauthoridChen, D=7405453271en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridWang, CA=7501646353en_HK