# Adaptive sampling for 2D functions with discontinuities

I have a 2D function, $f(x,y)$, which I can compute on a computer. The function is expensive to calculate, so I would like to use an adaptive sampling method to plot it in a region. That is, I want to use many sampling points in regions where the function is "interesting" and fewer where it is not so interesting (i.e. approximately constant or linear).

Question 1: I would like to avoid reinventing the wheel and having to figure out how to do this myself. Where can I read about adaptive sampling methods suitable for this purpose? I found out that "adaptive sampling" is not really the right keyword to Google for.

Question 2: I described the basic version of the method I am currently using here. This had to be complemented by an additional subdivision rule to ensure that the method converges equally fast everywhere: when retriangulation would remove an edge, that edge is subdivided as well. (This is merely a detail, if it turns out to be relevant, I'll describe it better, just ask in the comments...)

The main shortcoming of this method when used to sample my function is that it does not converge fast enough in regions where the contour lines of the function $f$ have a high curvature. Is it possible to improve the method so it'll generate more sample points where the curvature of the contour lines is high, or in regions where a discontinuity-line ends in a manner similar to a critical point of a phase diagram?

Some properties of my function: 1. It is bounded: $f(x,y) \in [0,1]$. 2. It has discontinuities: it has several (many) regions where it is either constant or varies relatively slowly, separated by discontinuities. 3. I compute it using a Monte Carlo simulation, so the value I get may not be completely accurate (the simulation might not reach a steady state). The adaptive sampling method must be robust enough to work well when there are a few (very few) incorrect values returned by the computation. This is one reason I didn't try to use any second derivatives of the function when deciding whether to subdivide the sampling mesh (the other reason being that it seems to be quite complicated to do when the mesh is irregular).

-
I'm primarily interested in some references (especially books) about adaptive sampling methods. To describe the method I use in sufficient detail, and explain the problems with it, would take a questions three times as long ... (so I am not sure it was good to include Question 2, but for now here it is) –  Szabolcs Apr 16 '12 at 13:51