2
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.