Before revision:  Previously, } O(n  \log n) time algorithms were known which are based on the technique for computing the minimum weight k-link path given in [A. Aggarwal et. al. DCG94;
After revision:  Building on the Rotate-and-Kill technique } O(n \log n) time algorithms were known which are based on the technique for computing the minimum weight k-link path given in [A. Aggarwal et. al. DCG94;