decomposition of non-convex objects

[Brad Barber]

I received the following request from John Nagle.  Any ideas?

Thanks for your help.
							--Brad

-----------------
X-Sender: nagle at shell5.ba.best.com
Date: Mon, 12 Apr 1999 19:06:06 -0800
To: Brad Barber <bradb at shore.net>
From: nagle at animats.com (John Nagle)
Subject: Decomposition into convex objects

    A problem related to convex hulling is the decomposition of a nonconvex
solid into convex solids.  This problem doesn't seem to be well-studied.
Is there any active work in that area of which you are aware?

    It's worth noting that, while the usual mathematical formulation of
this question is the decomposition of a nonconvex solid into a set of convex
solids whose sum is the original solid, a set of convex solids whose UNION
is the original solid would be equally useful for collision detection work.
That might be an easier problem.

    In fact, decomposition into a set of convex patches whose sum is the
surface of the original would be quite useful for collision detection,
and probably much easier than the other problems.  The hard problems
in convex decomposition mostly involve the creation of new interior
surfaces.

                                        John Nagle
                                        Animats
                                        www.animats.com




--------------------------------------------
Brad Barber   Cambridge MA   bradb at shore.net 
http://www.geom.umn.edu/locate/qhull  version 2.6

-------------
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://uiuc.edu/~sariel/CG/compgeom/threads.html.