File Download
There are no files associated with this item.
Supplementary

Citations:
 Scopus: 0
 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 

Authors  
Issue Date  2004 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3111, p. 150160 How to Cite? 
Abstract  This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNEgraph) of a given set of points V of size n in the kdimensional space (kD) for k = (2, 3). The NNEgraph 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 NNEgraph can also be used as a tool to test whether a point set is randomly generated or has some particular properties. We show in 2D that the NNEgraph 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 NNEgraph. The algorithm is optimal when d = O(log n). The algorithm is also sensitive to the structure of the NNEgraph, for instance when d = g · (log n), the number of edges in NNEgraph 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 3D, where d and d* are the Ω(log n/log log n)th largest vertex degree and the largest vertex degree in the NNEgraph, respectively. The algorithm is optimal when the largest vertex degree of the NNEgraph d* is O(log n/log log n). © SpringerVerlag Berlin Heidelberg 2004. 
Persistent Identifier  http://hdl.handle.net/10722/89149 
ISSN  2005 Impact Factor: 0.302 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Chan, MY  en_HK 
dc.contributor.author  Chen, D  en_HK 
dc.contributor.author  Chin, FYL  en_HK 
dc.contributor.author  Wang, CA  en_HK 
dc.date.accessioned  20100906T09:52:59Z   
dc.date.available  20100906T09:52:59Z   
dc.date.issued  2004  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3111, p. 150160  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/89149   
dc.description.abstract  This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNEgraph) of a given set of points V of size n in the kdimensional space (kD) for k = (2, 3). The NNEgraph 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 NNEgraph can also be used as a tool to test whether a point set is randomly generated or has some particular properties. We show in 2D that the NNEgraph 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 NNEgraph. The algorithm is optimal when d = O(log n). The algorithm is also sensitive to the structure of the NNEgraph, for instance when d = g · (log n), the number of edges in NNEgraph 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 3D, where d and d* are the Ω(log n/log log n)th largest vertex degree and the largest vertex degree in the NNEgraph, respectively. The algorithm is optimal when the largest vertex degree of the NNEgraph d* is O(log n/log log n). © SpringerVerlag Berlin Heidelberg 2004.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.title  Construction of the nearest neighbor embracing graph of a point set  en_HK 
dc.type  Article  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=13826905&volume=11&issue=4&spage=435 &epage= 443&date=2006&atitle=Construction+of+the+Nearest+Neighbor+Embracing+Graph+of+a+Point+Set  en_HK 
dc.identifier.email  Chin, FYL:chin@cs.hku.hk  en_HK 
dc.identifier.authority  Chin, FYL=rp00105  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.scopus  eid_2s2.035048843791  en_HK 
dc.identifier.hkuros  117583  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.035048843791&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  3111  en_HK 
dc.identifier.spage  150  en_HK 
dc.identifier.epage  160  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Chan, MY=7402597863  en_HK 
dc.identifier.scopusauthorid  Chen, D=7405453271  en_HK 
dc.identifier.scopusauthorid  Chin, FYL=7005101915  en_HK 
dc.identifier.scopusauthorid  Wang, CA=7501646353  en_HK 