Nearest-neighbor search in complex 3D scenes.
The nearest neighbor search problem arises in numerous fields of application, and its cost can become a performance bottleneck. It’s crucial to present effective data structures and methods optimized for this type of search operation and to estimate its complexity. We present and discuss an algorithm which performs a nearest neighbor search within a regular octree deployed for a 3D scene populated with large quantity of extended objects. The algorithm presented utilizes dynamic search boundary. We evaluate its average-case computational complexity for a model scene using probabilistic analysis.
Proceedings of XIX Baikal Conference "Information and Mathematical Technologies in Science and Management". Vol 3. Publisher: ISEM SB RAS, 2014. Pp. 56-62.