4 ms·
This isn't possible for some manifolds. In particular, you can't choose a point uniformly from an infinite plane. To see why, split the plane into an infinite
by panic 12y ago
This isn't possible for some manifolds. In particular, you can't choose a point uniformly from an infinite plane. To see why, split the plane into an infinite number of equally-sized (say, one by one) squares. Each square should have an equal probability that one of its points is chosen. Call this probability s.
Now let's look at the entire plane. If you pick a point, it will surely be on the plane. That means the probability that you choose a point on the plane is equal to one.
Putting the squares together gives you the whole plane, so you'd expect that summing their overall probabilities s would give you the overall probability of the plane, which is one. But there are an infinite number of squares, and there's no real number s for which the sequence s, s + s, s + s + s, ... converges to one.
- teraflop 12y agoWhat if we restrict our attention to closed manifolds? I guess the difficulty with framing this as an algorithmic problem is that it presupposes some way of specifying the input, and I don't know exactly how that would be done. If your input is a polygonal mesh (or higher-dimensional equivalent) then the problem is easy, but what about things like parametric surfaces?
- panic 12y agoYou probably mean bounded manifolds—the plane is closed (it contains all its limit points). The most general condition is that the manifold M itself has a positive, non-infinite measure m(M) (where m is the measure function). Then you can take the probability density of a set S to be m(S)/m(M). From this perspective, the problem with the plane is that it has an infinite surface area, so you can't divide by it to get a well-defined probability density. For parametric surfaces, here's a mathoverflow post answering your exact question: http://mathoverflow.net/questions/9991/how-can-i-sample-uniformly-from-a-surface http://mathoverflow.net/questions/9991/how-can-i-sample-unif... (ultimately linking to this SIGGRAPH paper: http://www.cs.virginia.edu/~jdl/bib/globillum/arvo01_notes.pdf http://www.cs.virginia.edu/~jdl/bib/globillum/arvo01_notes.p...)
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- enupten 12y agohttp://planetmath.org/anysigmafinitemeasureisequivalenttoaprobabilitymeasure http://planetmath.org/anysigmafinitemeasureisequivalenttoapr...
- panic 12y agoYes, but the probability measure they construct doesn't give "equal probability" in the sense that Xcelerate probably meant. Going back to the plane example, if we use the unit squares as our sequence A1, A2, ..., we'll get P(A1) = 1/2, P(A2) = 1/4, P(A3) = 1/8, and so on. This sums to 1 as you'd expect, but it's not uniform!
- apoklasdjasd 12y agoNote that the OP desired that "each point has an equal probability of being chosen". The infinite plane being infinite, this requirement does not formally make sense, but a natural way to interpret it is to ask for invariance under isometries (or translation-invariance). As the post that you replied to indicates, this is not possible for the Euclidean plane. The measure constructed by the lemma that you cite does not have this property.
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- alsdkalsjdalkd 12y agoLebesgue measure on R^n is sigma-finite.
- enupten 12y agoYes, I think the above is a fairly useless digression. Thank you for making me think more about this.
- leni536 12y ago> In particular, you can't choose a point uniformly from an infinite plane. While this is true, your reasoning is incomplete, you only arrive at the conclusion that s couldn't be positive. Why couldn't be s equal to 0? Note that a 0 probability event is not an impossible event and could still be in the event space. The problem is that there are countably infinite squares on the infinite plane so the measure of the infinite plane would add up to 0 instead of 1 by the property of the measure of countably infinite union of measurable sets.