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:


Source code of the library together with a demo program:

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.