Volume of N-dimensional object

[Aristotelis E. Charalampakis]

Hello NG,

This is a rather peculiar question. I will try to describe it as good as I
can.

Suppose we have a bounded N-dimensional space. For example, in 2 dimensions,
we have a rectangle with unit length edges.

This space is divided in two sub-spaces. We can produce points which lie on
the division surface.

The task is to calculate the volume of one of the two subspaces. ***We have
already used monte-carlo integration***; we need a faster approach.

Any hints?

TIA
Aristotelis

[Hans-Bernhard Broeker]

Aristotelis E. Charalampakis <arisN...@technologismikiremoveit.com> wrote:

> Suppose we have a bounded N-dimensional space.

Bounded by _what_? What kind of surface shape are we talking about here?

> This space is divided in two sub-spaces. We can produce points which lie on
> the division surface.

Again: divided by what kind of surface?

If "producing points" on the surface is all the information you have
about it then you're royally stuck. With input like that, even
determining for a single point on which side of the surface it is
would be a major challenge. Computing the volume, i.e. effectively
counting points on one side of the surface, would be almost
impossible.

> The task is to calculate the volume of one of the two subspaces. ***We have
> already used monte-carlo integration***; we need a faster approach.

Without restrictions to the shape of those volume's surfaces, odds are
there is none.

--
Hans-Bernhard Broeker (bro...@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

[Aristotelis E. Charalampakis]

Thank you for your prompt reply!

My knowledge in these fields is limited and my description was poor indeed;
however, I will try again:

Let's assume that we have a N-dimensional space. Each dimension of this
space represents a different design variable for a specific problem. The
design variables have an upper and a lower bound. The output of the problem
is boolean: true or false.

We can experiment with various values of the design variables and produce
the result of the problem, which can be true or false. Therefore, we know
the region in which our point lies.

With repetitive analyses, we can find points which are on the edge of the
"true" and "false" domains. We can use an approximation of some kind
(linear? Whatever is convenient, I suppose) that connects these points into
a N dimensional surface.

Apart from monte carlo integration (which is the obvious approach), is there
an alternative method of calculating the volume of either domain?

TIA,
Aristotelis

"Hans-Bernhard Broeker" <bro...@physik.rwth-aachen.de> wrote in message
news:32tldsF...@news.dfncis.de...

[Aleks Jakulin]

Break your object down into a simplicial complex. You can compute the
volume of each simplex. A simplex is a convex hull of (n+1) vertices:
{v_0,v_1,...,v_n}. Pick a certain vertex v_0. Now compute the norm of
the generalized vector product of the following vectors
[(v_1-v_0),(v_2-v_0),...,(v_n-v_0)]. Now divide this by n!, and that
is the volume. Here is the reference:

S. Cameron. A comparison of two fast algorithms for computing the
distance between convex polyhedra. IEEE Trans Robotics and Automation,
13(6):915-920, 1997.

Aleks

--
mag. Aleks Jakulin
http://www.ailab.si/aleks/
Artificial Intelligence Laboratory,
Faculty of Computer and Information Science,
University of Ljubljana, Slovenia.