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

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

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.

- Get the maximally separated nodes.

(This is the part where I really used some clever techniques.)

- Choose one of them as zero and the other's direction as the positive x-axis.

- Transform the coordinates.

- Calculate the normal mean on the transformed coordinates.

- 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