Re: Convex random polyhedrons

*To*: mathgroup at smc.vnet.net*Subject*: [mg85235] Re: Convex random polyhedrons*From*: danl at wolfram.com*Date*: Sat, 2 Feb 2008 23:35:35 -0500 (EST)*References*: <fnuhk1$9us$1@smc.vnet.net>

On Feb 1, 1:26 am, Steve Gray <stev... at roadrunner.com> wrote: > Does anyone have a handy way in Mathematica of making convex random > polyhedrons in 3D? The number of points should be a parameter. The > points do not have to be evenly spaced (obviously) and if up to say > 10% of them are not quite convex, that's ok. I have some ideas but > maybe it's already been done. > I know about ConvexHull3D.m and maybe that's the best way, but > it doesn't return the number of points, which must be computed. That > seems inefficient because the number of points must be exact. > > Steve Gray One method would be to find which new points are in the hull of the previous ones. If you choose pseudorandom points in some space (say, the unit cube) and according to some distribution, you would cast out any new ones in the hull of the earlier ones. A pedestrian check is to take all tetrahedra (from subsets of four points) and see if newcomers are in them. This would be something like O(n^5) complexity, not taking into account the ones you need to discard. A faster way might be to choose more points at random, enough to (with high probability) guarantee that the hull contains at least n points. Then use some method to find the hull, and randomly remove whatever number of points exceeds n. Daniel Lichtblau Wolfram Research