Simulating Uniform Points in a Convex Region From 1D Uniforms
You have access to a stream of independent Uniform$(0,1)$ random numbers. You want to generate points distributed uniformly over a two-dimensional region. First handle a simple shape (a rectangle or triangle). Then describe how to generate uniform points inside an arbitrary CONVEX region using only 1D uniform draws. One proposed shortcut maps the unit square's corners to the region's vertices and takes weighted averages of interior points -- does this produce a truly uniform distribution?
Hints
- Start with the triangle: a corrected barycentric construction (fold the unit square in half) gives uniform points.
- For a convex polygon, triangulate and pick a triangle with probability proportional to its area before sampling inside it.
- Check the proposed vertex-averaging map's Jacobian -- if it is not constant, the output density is not uniform; rejection sampling is the safe exact alternative.
Worked Solution
How to Think About It: Generating uniform points in 2D from 1D uniforms is standard for nice shapes, but the convex-region case has a subtle trap: convex combinations of vertices with uniform weights do NOT give a uniform distribution over the region. You need either rejection sampling or a correct area-weighted triangulation.
Simple shapes: - Rectangle $[0,a] \times [0,b]$: draw $U_1, U_2 \sim$ Uniform$(0,1)$, output $(aU_1, bU_2)$. Uniform by construction. - Triangle with vertices $P_0, P_1, P_2$: draw $U_1, U_2 \sim$ Uniform$(0,1)$; if $U_1 + U_2 > 1$ reflect via $U_1 \to 1-U_1$, $U_2 \to 1-U_2$ (or use $\sqrt{}$ trick); then point $= P_0 + U_1(P_1 - P_0) + U_2(P_2 - P_0)$. This IS uniform on the triangle.
Arbitrary convex region (polygon): 1. Triangulate the convex polygon into triangles (fan from one vertex). 2. Compute each triangle's area; pick a triangle with probability proportional to its area (using a 1D uniform to select). 3. Sample a uniform point inside the chosen triangle using the triangle method above. This gives an exactly uniform point over the whole region. For a smooth convex region, enclose it in a bounding box, sample uniformly in the box, and REJECT points outside the region -- rejection sampling is exact and simple.
Does the vertex-averaging shortcut work? NO. Mapping the unit square's four corners to four region vertices and taking a bilinear weighted average of a uniformly-sampled square point does not preserve uniformity. The Jacobian of a bilinear map is non-constant, so it bunches points -- areas get stretched and compressed unevenly. Concretely, convex combinations concentrate mass toward the centroid and distort density near the boundary. Uniform weights over vertices give a distribution peaked away from uniform.
Answer: For a rectangle or triangle, direct 1D-to-2D constructions give uniformity. For an arbitrary convex region, use area-weighted triangulation (choose a triangle by area, then sample within it) or rejection sampling against a bounding box. The vertex-averaging shortcut is NOT uniform because the mapping's Jacobian is not constant, so it distorts the density.
Intuition
The deep lesson is that uniformity is an area-preservation property, so any nonlinear (or even bilinear) reparameterization that does not have constant Jacobian will distort the density -- the tempting 'weighted average of corners' shortcut fails for exactly this reason. The two correct tools are area-weighted decomposition (sample a sub-region proportional to its area, then sample within it) and rejection sampling (exact, trivially correct, costs a constant factor in efficiency for convex shapes). This is foundational for Monte Carlo integration, generating initial conditions in simulations, and any time you must sample uniformly over a non-rectangular domain -- and the Jacobian check is the rigorous way to validate a proposed sampler.