From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci)
Subject: Re: efficient 3d-integration inside convex polyhedron?
Date: 2 Oct 2000 16:19:51 GMT
Newsgroups: sci.math.num-analysis
Summary: [missing]

In article <qgvgvbw8xk.fsf@umpa05.gwdg.de>,
 Joerg Behrens <jbehren@gwdg.de> writes:
|> Hello,
|> 
|> i want to integrate a smooth, expensive function f(x,y,z) inside a
|> convex polyhedron (one cell of a voronoi diagram).
|> 
|> For the case of a simple cubic 3d-box, i get sufficient accuracy
|> using the Gauss-Legendre method with 32 points in each dimension.
|> I use the simple scheme:
|> int(f,x=x1..x2,y=y1..y2,z=z1..z2)=int(int(int(f,x=x1..x2),y=y1..y2),z=z1..z2)
|> 
|> At first glance, for a more complicated polyhedron the problem just seems
|> to be that you have to determine the variable limits, e.g.: y1(x), z1(x,y).
|> But i expect problems in the convergence of the integral because the vertices
|> of the polyhedron will lead to kinks in the integrand of the 2. and 3.
|> dimension which are not well described by a finite set of Legendre polynoms.
|> I fear that even the integration of f(x,y,z)=const can not be done efficiently 
|> this way.
|> 
|> My question is: Is there an efficient integration method for integrands with
|> kinks besides a split into kink-free subregions......

I think this will not be so easy. even the case f==1 is not quite trivial.
what i found in my annotations is
(citation from jeff erickson)
""
>  I need to evaluate the volume of a polydedron in n-dimensional
> Euclidean space,
> the vertices of which lie on a polytope, in terms of the coordinates of
> its vertices.

I assume this means "Compute the volume of the convex polytope,
specified by its vertex coordinates."

>    * what the analytic formula is, or
>    * where to seek for an analytic formula, or

There is no such formula, even when n=3.  (You can cheat when n=2 by
listing the vertices in order.)  The volume depends on the combinatorial
structure of the polytope.

>    * if there exist a way to identify the simplexes this polyhedron is
>      formed of in order to evaluate the volume in terms of these
>      simplexes, or
This is one version of the classical "convex hull problem".  Several
algorithms are outlined in Ziegler's excellent "Lectures on Polytopes"
(Springer 1995).

>    * if there exists a code for me to integrate in my program, or

Yes.  Lots.  Perhaps the most useful for you is an implimentation by
Bueler, Enge, Fukuda, and Luthi, available from ETH Zurich:

        ftp://ftp.ifor.math.ethz.ch/pub/volume/

In addition to source code, the directory includes a PostScript
description of several algorithms and some experimental results.  Not
surprisingly, they find that different algorithms are more efficient for
different polytopes.

For other examples of convex hull code (which may or may not give you
the volume of the polytope), see either Nina Amenta's "Directory of
Computational Geometry Softwar"e, at the Geometry Center:

        http://www.geom.umn.edu/locate/cglist/ch.html
""

hope that helps
peter