Re: Integrating scattered data

[Jordi Gutiérrez Hermoso]

On 21/08/07, Thomas Shores <address@hidden> wrote:
> On Monday 20 August 2007 11:27:04 am Jordi Gutiérrez Hermoso wrote:
> > I have a surface in some irregular domain of R^2 that I'm sampling
> > at scattered, unstructured points. I'd like to find the volume
> > under this surface.
> >
> > Ideally, I'd like to not interpolate to points not in my data set,
> > since my surface is rather wiggly and I don't think interpolation
> > could be very accurate. A Delaunay triangulation is an obvious
> > first step, and then I could compose my surface of triangles to
> > get some sort of O(h) integration.
> >
> > Can I do better? Are there routines already in Octave to help me
> > do this? Is it possible to do some analogue of Simpson's rule to
> > get O(h^2) precision?
>
> Unless there is additional information about the data that you are
> not providing, it seems to me that deterministic methods don't make
> a whole lot of sense in this context.

It's a fairly regular surface whose values I only know at a few
scattered points, where "few" is of the order of 1e3. It oscillates
quite a bit, but it's supposed to be smooth, as it's supposed to be
the solution of a wave equation.

> You mention O(h), which I presume is something like the maximum
> distance between sample domain points.

"Linear" was my intent. Sure, h is the maximum distance between the
points. Well, the maximum of the minimum taken for each point.

> If your sampling is really unstructured, then you have little
> control over h,

It's not that unstructured. I can control h. It just doesn't fall in
general in any sort of nice grid. A Delaunay triangulation looks fine
and more or less regular, but I can't do much better than that. Some
triangles are slim, some are fat.

> usual order estimates (which are premised on h and factors such as
> reasonably small higher derivatives and regularity of the domain,
> which you suggest you may not have)

By regularity of the domain I didn't mean that the boundary isn't
Lipschitz. I merely meant that it isn't something as nice in general
as a box or a circle. We can assume the boundary is parametrised by
some C^\infty curve, though.

> Is the domain of function generating the surface even completely
> known?

Yes, but I'm approximating this surface by scattering points inside
this domain on its boundary in an unstructured manner.

> Moreover, by use of the word "sampling" you suggest that there might
> be error in your sampled values.  Is this so?

No. Perhaps it was a bad choice of words. What I meant to say is that
I don't know the surface's values at all points, only on my scattered
points.

> I'm assuming that what you are after the integral of a function
> f(x,y) over a recognizable bounded domain D in R^2.

Yes.

> What would make more sense is to me in this situation is a Monte
> Carlo method.

Ick. Can't do better?

> These have the disadvantages of relatively low accuracy and
> probabilistic estimates of error to boot,

And slow!

> but they have advantages of being relatively less sensitive to
> higher dimensional integration and ease of implementation.

Are two dimensions really that high dimensional? I was hoping I could
work with some kind of spline surface and integrate that spline
surface instead, which is what I meant when I spoke of a Simpson's
rule analogue.

> Do a google on something like "multivariate Monte Carlo methods" and
> you'll get a lot of information.

Let's call this Plan B. ;-)

I don't think my problem is ugly enough to warrant Monte Carlo
methods. Or do you disagree?

- Jordi G. H.