Can this problem be solved better than O(N^3)?

This problem is supposed to be solved in O(n^3) with small constant factor by author

Actually, O(N^2 log N) of geometry + O(N^3) of bit operations. This may give you an idea of the solution.