Given the local nature of the problem and the potential for using O(n) operations (as opposed n log n) my first suspect was wavelet transforms and sure enough p

Given the local nature of the problem and the potential for using O(n) operations (as opposed n log n) my first suspect was wavelet transforms and sure enough people have done that but that body of work seems more recent than the use of FFT.