1

I'm dealing with the problem of estimating the volume of a cloud of points in 16 dimensional space.

The points are from a grid and are discretised evenly in each dimension. Note also, I am assuming that all points come from the single connected volume. The only information I have for the problem is the dimensionality of the space (16) and the number of points (26,000,000).

I know I could wrap a convex hull around the points and return the volume, but because of the high number of dimensions and the large number of points, it takes way too long.

The approach I'm hoping to take, utilising the grid nature of the points, is to break it down into small 16 dimensional hyper cubes and count the number of those I have. Note - the volume doesn't have to be exact, it can be a rough estimate.

Here is a two dimensional example of the problem I'm dealing with - if I haven't made myself clear:

2D Example. In this example there are 11 points (with even spacing), and it forms 4 squares

How can I do a similar thing, for a 16 dimensional hypercubes? I can't see how the points are positioned, I just know I have 26,000,000 of them. How many 16 dimensional cubes do I have? A rough estimate is more than enough.

Thank you!

Mas
  • 11
  • You can project to lower dimensions to get estimates. Projecting down to a single dimension gives you the smallest and largest coordinate value in this dimension. Doing that for all 16 dimensions gives you a very rough upper bound (with a single hypercube). Looking at projections to 2 dimensions might reveal some additional structure in the data that is helpful. – quarague Jul 02 '19 at 09:25

0 Answers0