Skip to main content
1 vote

Fast construction of a static KD-tree without duplicates

You can use hashing to detect duplicates at insertion time. Assume you have your elements in an array $A[1,\dots,n]$. When inserting $A[i]$, you can apply an hash function $f$ to $A[i]$. If there is ...
SilvioM's user avatar
  • 933
1 vote

Visualizing How of KD-tree Data Structure Splits Space

The root will choose the split in one direction (in your case, (5,4) creates a vertical split). Then any nodes at the next level in your tree will split horizontally, then the nodes in the next level ...
JimN's user avatar
  • 849
1 vote

Lower bound for querying KD tree

No. To show a $\Omega(\sqrt{n})$ lower bound, it's not enough to show a lower bound for the single value $n=4$. I suggest you refer to the definition of big-Omega notation:
D.W.'s user avatar
  • 161k

Only top scored, non community-wiki answers of a minimum length are eligible