In IEEE 802.16, the wireless resources are logically partitioned into 5-ms frames, which extend in two dimensions: time and frequency. To break down the complexity of resource allocation at the base station, a split approach has been proposed in the literature, where the tasks of scheduling packets and allocating them into frames are solved in separate and subsequent stages. In this paper, we focus on the allocation task alone, which is addressed in its full complexity, i.e., by considering that data within the frame must be allocated as bursts with rectangular shape, each consisting of a set of indivisible sub-bursts, and that a variable portion of the frame is reserved for in-band signaling. After proving that the resulting allocation problem is NP-hard, we develop an efficient heuristic algorithm, called Recursive Tiles and Stripes (RTS), to solve it. RTS, in addition to handling a more general problem, is shown to perform better than state-of-the-art solutions via numerical analysis with realistic system parametrization. Furthermore, an extensive evaluation of the interaction between the scheduler and the allocator is carried out in a wide variety of network scenarios.