This content has been marked as final. Show 1 reply
swinte1 wrote:So for example, you have 5 points and you sort them by x and y coordinates in two separate arrays:
My question is, how can I build the arrays in linear time at each node? I have tried working it out on paper for the past few hours but lets say I sort the array using X first and I know that indices 0 - median will be on the left, however even if I had sorted the array by Y also, there is zero guarantee that all the points I need from x[0-median] will be in y[0-median]. They will obviously be included in x[0-median] but they will be sorted by x and not y, forcing me to resort at every single node.
x-list: 6 1 4 3 2 5
y-list: 6 5 1 2 3 4
Now you want just the points to the right of 4:
x-list: 3 2 5
y-list: 5 2 3
Create the x-list by iterating from the midpoint to the end.
Add each element in the x-list to a set..
Iterate through the y-list from left to right:
If the point in the y-list is contained in the set, add it to the new y-list.
This creates the arrays in linear time while keeping the points sorted. It does iterate over twice as many points in the y-list as needed though.