It seems that the shape of the outer one is not restricted to squares, but can also be rectangles?
I think the outer one could be any rectangle since we can generate uniform samples for rectangles easily. This square is just the smallest rectangle that encloses the circle.
I understand it is possible to do a more explicit version of a sphere, but is there an equivalent rejection sampling method for higher dimensions?
@nrauen Sure, you can just generate a random point in some cube (or rectangular bounding box), and then check if the point is within the shape you're interested in. For example, for a sphere, you could check if it is < r away from the sphere's center. But as you move to higher and higher dimensions, your probability of success decreases.