This seems very related to adaptive meshing algorithms, for which there are many naive formulations, and not all are intractable.