#kd #tree #interval #vec #k-dimensional


Implements a K-dimensional interval tree, for fast interval-overlap lookup. Binary-tree based implementation, i.e. O(log(n)) lookups.

2 releases

0.1.1 Feb 16, 2023
0.1.0 Feb 16, 2023

#771 in Data structures

MIT license

453 lines

K-dimensional Interval Tree

This crates implements a K-dimensional interval tree, based on a binary search (with the same complexity w.r.t operations).


  • Creation of the tree from a Vec
  • Overlap / inclusion test
  • Overlapping intervals retrieval
  • Overlapping volume computation

~~ That's all folks ~~


  1. Support insertion!
  2. ... and deletion, mutation in general
  3. Make API safer: how to get the desired behavior for the dynamic case?) -> without using more than one trait...
  4. Make API safer: add different overload when "borrowing" is desired, or exact same type is expected.
  5. Real benchmarks...