While many recent international video coding standards, especially H.264/MPEG-4 AVC, leverage block size adaptivity in motion estimation, the rate-distortion boundary can be pushed further by allowing even more freedom in the partitioning process of inter pictures. Adaptive-shape partitioning, which allows blocks to be partitioned along a straight line that runs through the block at a freely chosen angle and position, complements the regular subblock partitioning, allowing the encoder to better adapt to the local characteristics of the motion activity in a video sequence. However, the technique demands excessive encoder resources to exhaust the large search space. This paper is the result of an investigation into the relative rate-distortion importance of the various adaptive-shape modes, both in terms of the angle of the partition boundary and of its location within a block. We find that a significant reduction of the search space with a factor of up to 40 can be accomplished, while retaining 50 to 90% of the compression gain obtained in the state of the art. This allows encoders to operate at much lower complexity levels and also reduces the signaling overhead associated with adaptive-shape partitioning. Based on our observations, we formulate a number of approaches to trade off compression performance against encoder complexity. Furthermore we discuss the use of various schemes of overlapping motion estimation along the partition boundary, an aspect which is currently left unaddressed in the literature on adaptive-shape partitioning. We introduce the use of shape-adaptive transforms for the motion compensated signal, to avoid the condition that arises with adaptive-shape partitioning where a partition boundary lies inside a transform block. The result is a reduction in ringing artifacts while maintaining objective quality.