Re: [math-fun] Statistics for a class of random solids
Allan Wechsler <acwacw@gmail.com> wrote:
Suppose we have a random point generator, that generates points in R^3 with all three coordinates normally distributed around 0, say with a standard deviation of 1, though it doesn't really matter.
Do you mean that the values of the three coordinates are independently normally distributed, or that the distance from the origin is? It's not obvious to me that these would give the same distribution. I suspect that the former wouldn't be isotropic. I could be wrong.
Take N random points in this manner, and form the convex closure. This will be a polyhedron. What are the expected numbers of faces, vertices, and edges, in terms of N? Do they approach finite limits as N increases? I imagine that the surface area grows without bound. What about the expected number of faces that have 3, 4, 5, 6 edges, and so on?
I would expect that all the faces would be triangles, since the odds of any four or more of the N random points being coplanar is zero.
I can think of many more questions of this sort, and am wondering if anybody here knows what's known.
I have no idea, but I've been thinking about how to simulate it, so as to count the faces. Decades ago, I was tasked to simulate two random noise sources with a desired correlation. I decided to generate points whose distance from the origin was normally distributed and whose direction from the origin was uniformly distributed. The X coordinates of successive points would be one of the noise sources. To get the other noise source, I'd rotate the plane around the origin by an angle, and use the new X coordinate of the same successive points as the second noise source. The correlation depended on the angle, 1 for an angle of 0, 0.5 for an angle of 45 degrees, 0 for an angle of 90 degrees, -1 for an angle of 180 degrees, etc. (Digression: It's interesting that people can easily distinguish between white noise sources with different correlations when they're played into headphones. I'm not sure if anyone has figured out how this is neurologically possible.) To generate the random points, I generated a random (well, pseudorandom) K-bit bit string (as distinct from a random K-bit number in that leading zeros are allowed), where K is large, and set the distance from the origin equal to the number of one-bits in the string minus K/2 all divided by some appropriate scaling factor. The angle from the origin was then randomly generated uniformly from 0 to 360 degrees. But how would I do the same in three dimensions, as would be necessary for your problem? Doing the same, but separately with longitude and latitude, would cause a strong bias toward the poles. I finally decided that I'd generate points by randomly generating X coordinates uniformly between -1 and +1, likewise with Y coordinates and with Z coordinates. I would then discard any points whose distance from the origin exceeded 1 to carve the cube into a sphere. I'd stop when I had accumulated N non-discarded points. These should give uniformly distributed random directions from the origin. I'd combine those directions with the distances generated by counting 1-bits in N random K-bit strings. To find the convex closure, I'd check every set of three of these N points. If all other of the N points were on the same side of the plane defined by those three, then the resulting triangle is one of the faces of the convex closure polyhedron. I'm not really happy with that, since it's O(N^4), which is problematic for large N. It would be better if I could start by identifying which of the N points were part of the convex closure polyhedron. I could do that by seeing, for each of the N points, whether all other points were on the same side of some plane passing through the selected point. But how can I efficiently do that? There are so many possible planes to choose from.
Assuming "randomness" defined in a spherically symmetric manner, the resulting polyhedron will presumably resemble a lumpy sphere with occasional mountains. On the plains in between, most polygons will be triangles at 6-valent vertices. Whether mountains dominate plains would depend on the distribution tail --- I'd guess not for any reasonable extension of normal. [ Many years ago an astrophysicist requested a spherically symmetric pseudo-random distribution generator for his crater simulation, which I casually supplied and promptly forgot about. Every time the same question has popped up since, I have been utterly unable to reproduce it ... ] Computing the "convex hull" of a point set is a typical example of "geometric sorting" problems, to which computer graphics buffs have devoted considerable attention. Googling (ugh!) those terms should locate plenty of references. WFL On 3/9/19, Keith F. Lynch <kfl@keithlynch.net> wrote:
Allan Wechsler <acwacw@gmail.com> wrote:
Suppose we have a random point generator, that generates points in R^3 with all three coordinates normally distributed around 0, say with a standard deviation of 1, though it doesn't really matter.
Do you mean that the values of the three coordinates are independently normally distributed, or that the distance from the origin is? It's not obvious to me that these would give the same distribution. I suspect that the former wouldn't be isotropic. I could be wrong.
Take N random points in this manner, and form the convex closure. This will be a polyhedron. What are the expected numbers of faces, vertices, and edges, in terms of N? Do they approach finite limits as N increases? I imagine that the surface area grows without bound. What about the expected number of faces that have 3, 4, 5, 6 edges, and so on?
I would expect that all the faces would be triangles, since the odds of any four or more of the N random points being coplanar is zero.
I can think of many more questions of this sort, and am wondering if anybody here knows what's known.
I have no idea, but I've been thinking about how to simulate it, so as to count the faces.
Decades ago, I was tasked to simulate two random noise sources with a desired correlation. I decided to generate points whose distance from the origin was normally distributed and whose direction from the origin was uniformly distributed. The X coordinates of successive points would be one of the noise sources. To get the other noise source, I'd rotate the plane around the origin by an angle, and use the new X coordinate of the same successive points as the second noise source. The correlation depended on the angle, 1 for an angle of 0, 0.5 for an angle of 45 degrees, 0 for an angle of 90 degrees, -1 for an angle of 180 degrees, etc.
(Digression: It's interesting that people can easily distinguish between white noise sources with different correlations when they're played into headphones. I'm not sure if anyone has figured out how this is neurologically possible.)
To generate the random points, I generated a random (well, pseudorandom) K-bit bit string (as distinct from a random K-bit number in that leading zeros are allowed), where K is large, and set the distance from the origin equal to the number of one-bits in the string minus K/2 all divided by some appropriate scaling factor. The angle from the origin was then randomly generated uniformly from 0 to 360 degrees.
But how would I do the same in three dimensions, as would be necessary for your problem? Doing the same, but separately with longitude and latitude, would cause a strong bias toward the poles.
I finally decided that I'd generate points by randomly generating X coordinates uniformly between -1 and +1, likewise with Y coordinates and with Z coordinates. I would then discard any points whose distance from the origin exceeded 1 to carve the cube into a sphere. I'd stop when I had accumulated N non-discarded points. These should give uniformly distributed random directions from the origin. I'd combine those directions with the distances generated by counting 1-bits in N random K-bit strings.
To find the convex closure, I'd check every set of three of these N points. If all other of the N points were on the same side of the plane defined by those three, then the resulting triangle is one of the faces of the convex closure polyhedron.
I'm not really happy with that, since it's O(N^4), which is problematic for large N. It would be better if I could start by identifying which of the N points were part of the convex closure polyhedron. I could do that by seeing, for each of the N points, whether all other points were on the same side of some plane passing through the selected point. But how can I efficiently do that? There are so many possible planes to choose from.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Fred Lunnon -
Keith F. Lynch