WIL's blog

Need problems about kdtree?
By WIL, history, 9 years ago, In English

I recently studied this data structure, and resolved some problems, but I would like to solve other, if anyone can give me some problems, I would be grateful.

This are some problems that i solved by kdtree:

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's look like COJ is not accepting submissions :( Could someone help me? I think I got a working solution for the City Houses problem.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because of the covid situation, currently, in Cuba, the universities are close, this will probably take some time before being fixed

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Maybe I’m wrong, but as far as I know kd-trees can cave a complexity as bad as $$$O(N)$$$ per query for malicious inputs.

Also, what is the complexity of your solution to the third problem with KD-trees? I am pretty sure that $$$O(N^2)$$$ and even $$$O(N logN)$$$ can be achieved (it seems to me that you only have to count pairs that are neighbouring on the Voronoi diagram).

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Pupils should be solving array problems, not kdtree problems.

→ Reply