On the implementation of neighborhood search

[HyHuang1995]

Hi,

I am quite curious about the implementation in neighborhood search. As stated in this comment, radius search by kd-tree is experimentally faster than direct search by voxel hashing. This is quite different from the intuition that complexity for searching with kd-tree and voxel hashing are O(log(n)) and O(1), respectively. Any hints for this?

[koide3]

That comment was written by the author of the original NDT code in PCL. In that code, a strange neighborhood pattern was used for direct search (26 voxels: 3x3x3 except for center), and it largely affected the processing speed. I tried to replace it with more reasonable patterns (DIRECT1/7) and observed that in this setting direct search works better than radius search.