The variable size block motion compensation (VSBMC) technique is known to be more effective than the fixed-size block motion compensation technique (FSBMC) for video coding. However, the existing VSBMC techniques do not fully utilize the motion information of a frame for its partitioning. This paper presents a new adaptive partitioning scheme that utilizes more effectively the motion content of a frame in terms of the shape and size of the blocks. A new tree structure is proposed that allows not only the conventional four-to-one merge, but also three-to-one and two-to-one merges. This new VSBMC method results in a significantly improved rate-distortion performance. Test results of applying the proposed method on some MPEG video sequences are included.