C++ Kd-Tree library

This is a standalone C++ version of the kd-tree implementation in the Gamera framework that has been extended by a range search and has been relicensed by the original author under a BSD style license. It is written in plain C++98 and does not depend on any third party libraries. The interface was first described in:


A kd-tree is a data structure that allows for nearest neighbor queries in expected O(log(n)) time. The creation time of a kd-tree is O(n log(n)). This library offers four additional features not commonly found in kd-tree implementations:


A copy of the source code of the library together with a demo program can be found on Github. Here is the latest file release:

Authors and license

The code is copyrighted by Christoph Dalitz and Jens Wilberg, Institute for Pattern Recognition, Niederrhein University of Applied Sciences, Krefeld, Germany. It can be freely used under the terms a two-clause BSD-style license. Please cite the Technical report listed at the top of this page as a reference when building upon this code.