A first partitioning for partitioning a first region of a frame before a current frame in a video sequence is determined. The first partitioning defines at least two prediction sub-regions of the first region, and the prediction sub-regions include contiguous, non-overlapping groups of pixels. A motion vector that predicts a prediction sub-region of the first region is determined. The first partitioning is modified to a second partitioning by moving at least one border of the first partitioning that is between adjacent prediction sub-regions of the first region by the motion vector. A current region of the current frame that is collocated with the first region is partitioned by the second partitioning, and is encoded or decoded. The technique eliminates the need to re-partition an entire frame each time, and can be used with both rectangular-shaped block partitioning and partitioning using masks and other partitioning techniques.