[R] Concave hull

[(Ted Harding)]

On 26-Nov-09 21:11:02, baptiste auguie wrote:
> 2009/11/26 Ted Harding <Ted.Harding at manchester.ac.uk>:
>> Raising a rather general question here.
>>
>> This is a tantalising discussion, but the notion of "concave hull"
>> strikes me as extremely ill-defined!
>>
>> I'd like to see statement of what it is (generically) supposed to be.
> 
> I'm curious too, but I can imagine the following definition,
> 
> Consider a sphere (n-dimensional maybe) that we let come in contact
> with the scatter of points from outside. The set of points that the
> sphere can attain may define unambiguously (I think) a concave hull,
> for a specified sphere radius. The convex hull is obtained in the
> limit of infinite radius (plane).
> 
> It's probably not exactly this, but I guess that's the rough idea.
> 
> Just a thought,
> baptiste

Yes, it's the sort of idea I have had too! I imagined the true convex
hull as made of a stretchable material (like a soap bubble). With that
in place, now gently raise the air pressure outside the bubble. This
pushes the envelope inwards.

When the envelope, moving inwards, meets a point, it sticks to it and
does not move further at that point.

The parameter under your control is the pressure. You can stop when
you feel like it.

Once you have stopped, the set of points in contact with the envelope
can then be joined by lines (or, in higher dimensions, faces/simplexes).

This even has the merit that the surface has a definite equation
(with boundary conditions), so could be programmed!

However, the main thing left hanging in the air by this idea is that
you may want to arrange things so that the envelope gets pushed further
in from some directions than from others -- i.e. on the soap-bubble
analogy, you want to apply different levels of extra pressure to
different parts of the envelope.

For instance, in the example I included in my previous post, you might
want the envelope between points 19 & 3 to be under greater pressure
than the envelope between points 13 & 17.

So it is still an undefined solution. As is yours -- since you might
want to use different radii of spheres from different directions.

Ted.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <Ted.Harding at manchester.ac.uk>
Fax-to-email: +44 (0)870 094 0861
Date: 26-Nov-09                                       Time: 21:45:47
------------------------------ XFMail ------------------------------