Tuesday, July 26, 2011

This is hard !!!

So I encountered some problems in my centroid calculation algorithm, which I am trying to correct but I really wanted to see why am I implementing the algorithm that I have mentioned in the last to last post rather than the naive algorithm.

This gives a time complexity of O(n log n) over naive O(n^2) which would have certainly been easier. But I think this would save appreciable computational cycles.

Assuming that we are working with 4000nodes. And considering the average number of children a node has to be 8. Then here are the comparisons.

Naive Algorithm.
64 X 4000 = 256,000

New algorithm.
24 X 4000 =  96,000

Here are the steps in the new in-centroid calculation.

  1. Get the maximally separated nodes.
    (This is the part where I really used some clever techniques.)
  2. Choose one of them as zero and the other's direction as the positive x-axis.
  3. Transform the coordinates.
  4. Calculate the normal mean on the transformed coordinates.
  5. Transform back.

This  is difficult to code, requires extreme patience and there are so many cases ; I need to finish it fast.

No comments:

Post a Comment