Approximation algorithms for problems in P
As Jukka points out, computational geometry is a rich source of problems that can be solved in polynomial time, but we wish to get fast approximations. The classic "ideal" result is an "LTAS" (linear time approximation scheme) whose running time would be of the form $O(n + \text{poly}(1/\epsilon))$ - usually these are obtained by extracting a constant (poly($1/\epsilon$)) sized kernel from the data, and running an expensive algorithm on that kernel, with a guarantee that an exact solution on the kernel is an approximate solution on the entire input. 

There are a number of tricks, reductions and principles, and Sariel Har-Peled's new book is full of these. I don't think there's a rich complexity theory as such.