# Determine amount of overlap of N k-dimensional point clouds

in the area of image processing, I'm trying out different dimensionality reduction techniques. I use these to reduce intensity images/bitmaps (sliced as a vector, i.e. such a vector has a high dimensionality, e.g. 6400 for a 80x80 image) to a lower, k-dimensional space (e.g. k=12). One of these techniques is PCA, and as you know, there are many others.

Given:

• N point clouds (i.e. a set of k-dimensional real-valued coordinates, refered to as "point")
• Each point cloud has some number of points (e.g. n_i)
• No knowledge about the distribution of the points for each point cloud shall be assumed (although it's probably somehow Gaussian-like distributed, but not uni-variate)

Needed: the amount of overlap of these point clouds. Or, in other words, how separable the data is. I really have no clue how intensive of a problem this is. Visually, I conceive the solution like building the k-dimensional convex hull for every point cloud, calculating the volume of total overlap.

If the distribution was just "spherical" (i.e. uni-variate Gaussian) it would be trivial, I could simply divide 'no of points that are further away from their own cloud center than 0.5*distanceToCenterOfOtherClosestPointCloud' by 'total no of points'

I'm also sorry if I should have made use of the wrong tags. I'm by no means a mathematician.

-
The question is rather vague (and even your "trivial" case is not so). Some issues: the "overlap volume" of a pair of "clouds" might no be representative (the concentration of points does not matter? what if class A has a high overlap voulmen with class B, but only because of a few points?). Are we interested in pair-overlapping only? (assume class A overlaps 50% of its cloud with class B, and 50% with class C; does it matter whether it's the same half?) Here's a little paper: prasa.org/proceedings/2004/prasa04-12.pdf – leonbloy Jul 2 '12 at 17:18
You're totally right, I was not clear with my question. The paper you provide is a very good start, thanks! Class separability measures being the keyword here. – NameZero912 Jul 2 '12 at 21:30