Hi,
what is a smart algorithm for this?
Input data: List L of rectangles. Rectangle is 4 ints: (x, y) of top-left corner, (xl, yl) the two lengths. Also input data is exactly one torus map M -- this is a large rectangle, it's larger than any single rectangle in L.
Wanted output: Rectangle O that surrounds all the listed rectangles. This rectangle should be as small as possible. It's allowed to move the rectangles in L by integer multiples of the length of M. The output rectangle O should account for O-minimizing optimal shifts of the rectangles in L. (To clarify after NaOH's question: I want to minimize the lengths of O. You may shift the rectangles of L as often as you wish to minimize the length of O.)
I know: You can separate this problem by dimension: Consider only x and x-length first, then y and y-length.
Existing algorithms: I have an algorithm to find the smallest container on a non-torus map -- when you're not allowed to move the rectangles in L by the length of M.
For example, if the rectangles are denoted as Rect(x, y, xl, yl), the non-torus algorithm computes the correct smallest container for the following list of three rectangles:
[ Rect(3, 5, 10, 10), Rect(5, 5, 9, 9), Rect(1, 1, 1, 1) ]
.reduce!smallestContainer == Rect(1, 1, 13, 14)
I also have an exptime algorithm for the torus-smallest container: For each rectangle in the input list, try whether to set its top-left point in the range [0, M.xl[ or into [M.xl, 2 * M.xl[ instead. With an input list of length n, we have 2n choices to try. For each choice, measure with the non-torus algorithm. Use the choice that minimizes the non-torus algorithm target value.
Can I do it in less than exptime?
-- Simon