File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10878-006-8459-0
- Scopus: eid_2-s2.0-33744547037
- WOS: WOS:000237795700007
- Find via
Supplementary
- Citations:
- 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 | |
Keywords | Computational Geometry Nearest Neighbors Network Connections |
Issue Date | 2006 |
Publisher | Springer 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? |
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 Θ (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 Identifier | http://hdl.handle.net/10722/152335 |
ISSN | 2015 Impact Factor: 1.08 2015 SCImago Journal Rankings: 1.093 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, MY | en_US |
dc.contributor.author | Chen, DZ | en_US |
dc.contributor.author | Chin, FYL | en_US |
dc.contributor.author | Wang, CA | en_US |
dc.date.accessioned | 2012-06-26T06:37:16Z | - |
dc.date.available | 2012-06-26T06:37:16Z | - |
dc.date.issued | 2006 | en_US |
dc.identifier.citation | Journal Of Combinatorial Optimization, 2006, v. 11 n. 4, p. 435-443 | en_US |
dc.identifier.issn | 1382-6905 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/152335 | - |
dc.description.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 Θ (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.language | eng | en_US |
dc.publisher | Springer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905 | en_US |
dc.relation.ispartof | Journal of Combinatorial Optimization | en_US |
dc.subject | Computational Geometry | en_US |
dc.subject | Nearest Neighbors | en_US |
dc.subject | Network Connections | en_US |
dc.title | Construction of the nearest neighbor embracing graph of a point set | en_US |
dc.type | Article | en_US |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_US |
dc.identifier.authority | Chin, FYL=rp00105 | en_US |
dc.description.nature | link_to_subscribed_fulltext | en_US |
dc.identifier.doi | 10.1007/s10878-006-8459-0 | en_US |
dc.identifier.scopus | eid_2-s2.0-33744547037 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33744547037&selection=ref&src=s&origin=recordpage | en_US |
dc.identifier.volume | 11 | en_US |
dc.identifier.issue | 4 | en_US |
dc.identifier.spage | 435 | en_US |
dc.identifier.epage | 443 | en_US |
dc.identifier.isi | WOS:000237795700007 | - |
dc.publisher.place | Netherlands | en_US |
dc.identifier.scopusauthorid | Chan, MY=7402597863 | en_US |
dc.identifier.scopusauthorid | Chen, DZ=7405453271 | en_US |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_US |
dc.identifier.scopusauthorid | Wang, CA=7501646353 | en_US |
dc.identifier.citeulike | 669791 | - |