Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other point, and the edges of all rectangles must be parallel to the coordinate axes.
For example, 1 rectangle can contain all n points, but if it can be subdivided into 2 rectangles where each rectangle contains p points, then that would make k=2 if the rectangles could not be subdivided further.
Alternatively, n rectangles, each of which contains 1 point, could be constructed and iteratively merged together until all rectangles contain p points.
Is there an efficient algorithm in m dimensions?