File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleConstruction of the nearest neighbor embracing graph of a point set
Authors
KeywordsComputational Geometry
Nearest Neighbors
Network Connections
Issue Date2006
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2006, v. 11 n. 4, p. 435-443 How to Cite?
AbstractThis 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 Θ (n2) time in the worst case. We also present an O(n log n + nd) time algorithm, where d is the Ω(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 · (log n), the number of edges in NNE-graph is bounded by O(gn log n) for any value g with 1 ≤ g ≤ 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(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).
Persistent Identifierhttp://hdl.handle.net/10722/152335
ISSN
2015 Impact Factor: 1.08
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, MYen_US
dc.contributor.authorChen, DZen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorWang, CAen_US
dc.date.accessioned2012-06-26T06:37:16Z-
dc.date.available2012-06-26T06:37:16Z-
dc.date.issued2006en_US
dc.identifier.citationJournal Of Combinatorial Optimization, 2006, v. 11 n. 4, p. 435-443en_US
dc.identifier.issn1382-6905en_US
dc.identifier.urihttp://hdl.handle.net/10722/152335-
dc.description.abstractThis 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 Θ (n2) time in the worst case. We also present an O(n log n + nd) time algorithm, where d is the Ω(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 · (log n), the number of edges in NNE-graph is bounded by O(gn log n) for any value g with 1 ≤ g ≤ 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(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).en_US
dc.languageengen_US
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_US
dc.relation.ispartofJournal of Combinatorial Optimizationen_US
dc.subjectComputational Geometryen_US
dc.subjectNearest Neighborsen_US
dc.subjectNetwork Connectionsen_US
dc.titleConstruction of the nearest neighbor embracing graph of a point seten_US
dc.typeArticleen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s10878-006-8459-0en_US
dc.identifier.scopuseid_2-s2.0-33744547037en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33744547037&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume11en_US
dc.identifier.issue4en_US
dc.identifier.spage435en_US
dc.identifier.epage443en_US
dc.identifier.isiWOS:000237795700007-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChan, MY=7402597863en_US
dc.identifier.scopusauthoridChen, DZ=7405453271en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridWang, CA=7501646353en_US
dc.identifier.citeulike669791-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats