This isn’t homework, before anyone asks; it’s a discussion we’ve been wrestling with for a while now, so I turn to the combined wisdom of the Dope to assist us in trying to solve it.
I have a cloud of points in n-dimensional space, and want to find the volume of the convex polyhedron that these points define. In 2D space, I have found a systematic and simple way of doing it, but we’re not clear how that would generalise to N dimensions. Is there a standard way of a) determining the points that are the vertices and b) calculating the volume of this polyhedron? I don’t need an exact value; a numerical approximation would do, provided it was reasonably accurate. Any suggestions or places I can look that would help in solving this seemingly intractable problem?
Could a passing mod change the title from “polygon” to “polyhedron”? Thanks.
This is not something I’m familiar with, but I am aware of Pick’s Theorem, so I checked to see if there is a higher dimensional analogue of that. I found this, which looks like a good starting point, at least.
Even finding which points are the vertices is probably going to be tricky. If I had to do this, I think I’d do a Monte Carlo approximation: Find some simple larger volume that completely encompasses your cloud (probably a hypercube or hyper-rectangular prism), pick a point at random within that volume, then figure out a way to determine if that point is inside or outside the convex hull of the polygon. Repeat a few thousand times, and the proportion of points that fall inside the hull is the ratio of the volume of the hull to the volume of the containing box.
Isn’t this basically computing the volume of an n-dimensional convex hull? There are algorithms for that, like quickhull.
This is what you want. A Monte Carlo algorithm would be great if there were a simple way to compute whether a point is in the convex hull without going through the trouble of computing it, but I don’t know of any good way to do so in general.
Thanks for your help, all. Part of the problem was not knowing the terminology - I’d never heard the term “convex hull” before researching this, so we didn’t know where to start looking.
I’m looking into qhull; it seems as though it’s capable of doing what I need. I’m just a little concerned that it may be computationally too complex, as we have 125 points in 26 dimensions. But I’m going to gradually build up to that and see where it goes. Cheers again!