Assume spawn(e) spawns points uniformly within an element e, i.e., for any i∈e, P⁢(i∣e)=1v⁢(e), where P⁢(i∣e) is the probability density function describing the likelihood of sampling a point i within the element e, and v⁢(e) is the volume of e. Let 𝒮 be the set of all solutions satisfying constraints 𝒞. The probability of sampling i∈(ℐ∪𝒪) involves selecting an element e∋i and spawning i uniformly within e. The selection probability of e is proportional to its volume:

Thus, the joint probability of selecting e and spawning i is:

Now, a point sampled with this process, without proper rejection, may not belong to 𝒮. If e∈ℐ, all points i∈e satisfy 𝒞, so i is always accepted. If e∈𝒪, i is accepted only if i∈𝒮, and otherwise we repeat the sampling process. It follows that Algorithm 3 returns a particular solution i∈𝒮 either if:

• ■

  it samples i at the first attempt,

• ■

  or if the first attempt fails to produce a solution and i is sampled in a subsequent attempt.

The probability of sampling a particular solution i∈𝒮 is thus

where P⁢(fail) is the probability that a uniform element in ℐ∪𝒪 does not satisfy 𝒞. This is constant for all i∈𝒮, proving uniformity.