The problem of deciding whether x ∈ Z ⁿ is a member of a scale-invariant and rationally dispersed W ∈ &RR; ⁿ has complexity &OHgr; ( log ₂ β ( W ) - 2 n ) in the algebraic tree model, where β ( W ) is the number of connected components of W that are of positive measure. Working in this context, the author obtains tight lower bounds for a large class of problems, including element distinctness, set disjointedness, finding convex hull, integer max gap, and closest pair of a simple polygon.