Union of 3D polyhedra

[Saurabh Sethia]

Dear Geometers:

I need a reference that gives the best known theoretical upper bound on
the complexity of computing the union of a bunch of simple polyhedron in 3D.
Let the total size of all polyhedrons be $n$.  Let the size of union be $u$.
And let the size of the arrangement of these polyhedrons be $a$.  While it will
be nice to have a result in terms of $n$ and $u$, I will be happy if I find
a reference that gives a bound in terms of $n$ and $a$.

It will also be useful to me to know the upper bound if the polyhedrons were
convex.  Note that I need the algorithmic complexity and not a combinatorial
bound on the output size.

I have looked at the two computational geometry handbooks but havn´t found
anything.  Please send me email if you know about this.  I will post a
summary of responses I receive (if any).

thanks,
--saurabh


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.