A Fast k-Neighborhood Algorithm for Large Point-Clouds

Simple item page
dc.contributor.authorSankaranarayanan, Jaganen_US
dc.contributor.authorSamet, Hananen_US
dc.contributor.authorVarshney, Amitabhen_US
dc.contributor.editorMario Botsch and Baoquan Chen and Mark Pauly and Matthias Zwickeren_US
dc.date.accessioned2014-01-29T16:38:14Z
dc.date.available2014-01-29T16:38:14Z
dc.date.issued2006en_US
dc.description.abstractAlgorithms that use point-cloud models make heavy use of the neighborhoods of the points. These neighborhoods are used to compute the surface normals for each point, mollification, and noise removal. All of these primitive operations require the seemingly repetitive process of finding the k nearest neighbors of each point. These algorithms are primarily designed to run in main memory. However, rapid advances in scanning technologies have made available point-cloud models that are too large to fit in the main memory of a computer. This calls for more efficient methods of computing the k nearest neighbors of a large collection of points many of which are already in close proximity. A fast k nearest neighbor algorithm is presented that makes use of the locality of successive points whose k nearest neighbors are sought to significantly reduce the time needed to compute the neighborhood needed for the primitive operation as well as enable it to operate in an environment where the data is on disk. Results of experiments demonstrate an order of magnitude improvement in the time to perform the algorithm and several orders of magnitude improvement in work efficiency when compared with several prominent existing method.en_US
dc.description.seriesinformationSymposium on Point-Based Graphicsen_US
dc.identifier.isbn3-905673-32-0en_US
dc.identifier.issn1811-7813en_US
dc.identifier.urihttps://doi.org/10.2312/SPBG/SPBG06/075-084en_US
dc.publisherThe Eurographics Associationen_US
dc.subjectCategories and Subject Descriptors (according to ACM CCS): I.3.6 [Computer Graphics]: Methodology and Techniques; I.3.8 [Computer Graphics]: Applications;en_US
dc.titleA Fast k-Neighborhood Algorithm for Large Point-Cloudsen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
075-084.pdf
Size:
296.86 KB
Format:
Adobe Portable Document Format
Download
Collections
Symposium on Point Based Graphics 06