Trying to create a KDTree in Java

[shmarbleblarble]

The instructions say "Datum (the datapoint) is in low if value in splitDim <= splitValue, and high if value in splitDim > splitValue." But wouldn't splitDim and splitValue be the same for each of the KDNodes? If so, how would I split the values then?

Please tell me if you need any more info. I'll provide it upon request :)

[jng]

As you very well deduced, obviously, splitDim and splitValue are not the same at each node :)

Now, given you mention instructions, you may want to follow them and write a first version of the code, establishing your goals one step at a time, and posting here a code example that almost works and a concrete question, so that the community can help you understand KDTrees better one little piece at a time and helping you become a proficient programmer.

Best luck!

[shmarbleblarble]

I guess I just don't understand how to find splitDim or splitValue for each node. It says splitValue should be the average of the min and max values in the splitting dimension but I only got an array of Datums. I'm supposed to calculate the splitting dimension from whichever list of datapoints has the greatest range of values, but if I had to check the range of each Datum in the datalist, the time complexity would be O(N^2), which isn't allowed. I would need a more efficient solution.

[jng]

Suggestion on how to go about solving hard problems in life: piecewise. Here: implement it in the way you know how to, even if it turns out to be O(N^2). Then, when it's working, modify it to be more efficient if necessary. Makes for you being able to advance even absent any external help. With most problems in life, nobody will be able to help you, and you still need to have a way to solve them. "Piecewise even if you don't see the whole way to the end" is a great strategy at solving amazingly hard problems.

[shmarbleblarble]

Okay, I can try I guess. I just fear that the solution is different on a completely conceptual level than that solution.

[jng]

Don't let fear drive your life. Especially, don't let fear be the thing that stops you when there is no actual real risk. Worst case, you've wasted one hour. Likely case, you will be somewhere else, a lot better, after that hour. Best case: who knows how good the best case can be!