[task #15713] Make quad structure to make unique hashes of 4 objects

[Sachin Kumar Singh]

Follow-up Comment #19, task #15713 (project gnuastro):

For the kd-tree, I have a bit dilemma on choosing the type of implementation.
In one implementation(as given in its Wikipedia) it uses median to build the
tree. But in another, it is also possible to build a tree without median(using
only the axis to determine the next child). Also, it is mentioned in its
Wikipedia page that,

Note that it is not required to select the median point. In the case where
median points are not selected, there is no guarantee that the tree will be
balanced. To avoid coding a complex O(n) median-finding algorithm or using an
O(n log n) sort such as heapsort or mergesort to sort all n points, a popular
practice is to sort a fixed number of randomly selected points and use the
median of those points to serve as the splitting plane. In practice, this
technique often results in nicely balanced trees.


Now it is desired/recommended to use a balanced tree for proper tree heights
and skewness and hence fast operations. But if I choose the one with median,
I'll have to make the array beforehand rather than inserting the hashes as
they are made, which is a better and more modular design. What do you
suggest?

P.S- Both kinds of implementation are ready to be tested after this minor
problem is solved:-)

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/task/?15713>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/