MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Convex random polyhedrons

  • To: mathgroup at
  • Subject: [mg85235] Re: Convex random polyhedrons
  • From: danl at
  • Date: Sat, 2 Feb 2008 23:35:35 -0500 (EST)
  • References: <fnuhk1$9us$>

On Feb 1, 1:26 am, Steve Gray <stev... at> 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

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

  • Prev by Date: Efficient way of reading matrices
  • Next by Date: How edit a saved palette?
  • Previous by thread: Re: Convex random polyhedrons
  • Next by thread: Re: front end commands