Accelerating kd-tree Searches for all k-nearest Neighbours
| dc.contributor.author | Merry, Bruce | en_US |
| dc.contributor.author | Gain, James | en_US |
| dc.contributor.author | Marais, Patrick | en_US |
| dc.contributor.editor | M.- A. Otaduy and O. Sorkine | en_US |
| dc.date.accessioned | 2014-01-26T14:58:16Z | |
| dc.date.available | 2014-01-26T14:58:16Z | |
| dc.date.issued | 2013 | en_US |
| dc.description.abstract | Finding the k nearest neighbours of each point in a point cloud forms an integral part of many point-cloud processing tasks. One common approach is to build a kd-tree over the points and then iteratively query the k nearest neighbors of each point. We introduce a simple modification to these queries to exploit the coherence between successive points; no changes are required to the kd-tree data structure. The path from the root to the appropriate leaf is updated incrementally, and backtracking is done bottom-up. We show that this can reduce the time to compute the neighbourhood graph of a 3D point cloud by over 10%, and by up to 24% when k | en_US |
| dc.description.seriesinformation | Eurographics 2013 - Short Papers | en_US |
| dc.identifier.issn | 1017-4656 | en_US |
| dc.identifier.uri | https://doi.org/10.2312/conf/EG2013/short/037-040 | en_US |
| dc.publisher | The Eurographics Association | en_US |
| dc.subject | I.3.5 [Computer Graphics] | en_US |
| dc.subject | Computational Geometry and Object Modeling | en_US |
| dc.subject | Object hierarchies | en_US |
| dc.title | Accelerating kd-tree Searches for all k-nearest Neighbours | en_US |