Efficient Shamir secret sharing reconstruction
Yes. If you choose the evaluation poitns for the polynomial carefully, this problem is the same as correcting erasures in the Reed-Solomon encoding of a message, and there are faster algorithms for that problem. 

http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction