A theoretical frame work for rate-constrained motion estimation is introduced. The best trade- off between displacement vector rate and prediction error rate is shown to be the point were the partial derivatives of the multivariate distortion rate function are equal. Low bit-rate coders are severely rate-constrained, and coarser motion compensation is appropriate for lower bit- rates. A new region-based motion estimator builds a tree of nested regions from back to front, where each region is encoded by a closed B-spline contour. The rate-constraint is a natural termination criterion when building the region tree. Experimental results show that rate- constrained motion compensation is superior to a full-search block matching scheme when incorporated into a motion-compensating hybrid coding scheme, yielding up to 3 dB SNR improvement at 15 kbps.