Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [kd-tree]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
156 views

### Visualizing How of KD-tree Data Structure Splits Space

I am trying to understand how KD-tree works when we insert a node and how it splits the xy plane, please. Below $[5, 4]$ splits the xy-plane into left and right parts while $[2,6]$ splits it into top ...
• 505
In the book Computational Geometry, Algorithms and Applications there is an exercise asking: In the proof of the query time of the kd-tree we found the following recurrence: $$Q(n)= \begin{cases}O(1)... • 190 2 votes 1 answer 68 views ### Kd-trees excluding some splitting dimensions I have a 12-dimensional state-space and would like to use a kd-tree to partition my data, so that nearest neighbour operations can be performed quickly. Unfortunately I have the issue that three of ... • 143 2 votes 0 answers 127 views ### Adaptive kD-trees In classical kD-trees, the splitting dimension is chosen using a simple and systematic rule: dimensions are taken in a round-robin fashion. But extra freedom is available because you could very well ... 0 votes 1 answer 71 views ### Fast construction of a static KD-tree without duplicates From what I know, the classic way of constructing a KD-tree is with alternating dimensions and finding median at each level. In my dataset, I have a lot of duplicated points, and I want to incorporate ... • 127 0 votes 0 answers 40 views ### Rank of random binary string with Bernoulli distribution For 1\ge p_1 \ge \dots \ge p_n \ge 0, and for i\in[n] draw k iid binary strings with m length:$$X_{i,1},\dots,X_{i,k}\stackrel{iid}{\sim} \text{Bernoulli}(p_i)^m. Viewing these binary ...
Suppose given $n$ pair of points $P=\{(p_1,q_1),\dots,(p_n,q_n)\}$ in the plane that each pair $(p_i,q_i)\in \mathbb{R}^2$ can't belong to the same group. We want to partition points into $K$ groups ...