It seems to me that most presented algorithm have quadratic complexity. They are O(n\ \log n) versions for planar points (see below). Maybe this could be adapted to your case. Nevertheless, complexity analysis seems absent from this thread.
S. Felsner and L. Wernisch. Maximum k-chains in planar point sets:
Combinatorial structure and algorithms. SIAM Journal on Computing;
M. Jensen. Reducing the run-time complexity of multiobjective EAs:
The NSGA-II and other algorithms. IEEE Transactions on Evolutionary
Computation, 7(5):503–515, 2003."