Questions tagged [kd-tree]
The kd-tree tag has no usage guidance.
5
questions
2
votes
1
answer
27
views
Visualizing How of KD-tree Data Structure Splits Space
Not sure if I can use a figure, but 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 ...
- 493
2
votes
0
answers
88
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 ...
- 8,871
0
votes
0
answers
35
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 ...
- 531
2
votes
1
answer
106
views
Lower bound for querying KD tree
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
0
votes
0
answers
97
views
Find a bipartition of points using blackbox
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 ...
user146750